1. Sum of two numbers

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

Example 1:

Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

Example 2:

Input: nums = [3,2,4], target = 6Copy the code

Example 3:

Input: nums = [3,3], target = 6Copy the code

1. First of all, we should make sure that the array in the problem is ordered. If the problem is not explicitly stated, we generally think of it as unordered, and in the case of unordered, except for brute force, we should consider using hash tables, which are O(N) in time and space.

class Solution:
    def twoSum(self, nums: List[int], target: int) - >List[int] :
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i
        return []
Copy the code

2. But what if they say given an ordered array? Is there any other optimization plan? The answer is yes! Using double Pointers in ordered case, time complexity O(N), space complexity O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) - >List[int] :
        left, right = 0.len(nums) - 1
        while left < right:
            sum = nums[left] + nums[right]
            if sum == target:
                return [left, right]
            elif sum > target:
                right -= 1
            else:
                left += 1
        return []
Copy the code

771. Gems and stones

You are given a string jewels representing the type of stone in the stone and a string stones representing the stones you own. Stones each character represents a type of stone you own and you want to know how many of the stones you own are gems.

The letters are case sensitive, so “A” and “A” are different types of stone.

Example 1:

Input: jewels = "aA", stones = "aAAbbbb" Output: 3Copy the code

Example 2:

Jewels = "z", stones = "ZZ" Output: 0Copy the code

1. The simplest idea would be to use a double loop, but that would be O(N^2) time, which we don’t want. In Python, there are two important types of hash structures. Using hash structures, we can reduce the time of in operations to determine whether an element is in a container from O(N) to O(1). The first type of hash structure is set. The space complexity is order M.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) - >int:
        jewelsSet = set(jewels)
        return sum(s in jewelsSet for s in stones)
Copy the code

2. The second type of hash structure is dict, and the Counter container is an advanced dict that can record the number of occurrences of each element. The following algorithm has a time complexity of O(M+N) and a space complexity of O(Len (set(stones))

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) - >int:
        counter = Counter(stones)
        return sum(counter[i] for i in jewels)
Copy the code