The first question of LeetCode brushing questions, the use of the sum of two numbers and the hash table

Topic description

Given an integer array nums and a target value target, please find the two integers in the array whose sum is the target value, and return their array indices.

You can assume that there will only be one answer for each input. However, the same element in an array cannot be used twice.

Example: Given nums = [2, 7, 11, 15], target = 9
because nums[0] + nums[1] = 2 + 7 = 9
So return [0, 1]

Method 1: Solve with the related functions of list in Python

Idea: The key to solving the problem is to find whether "num2=target-num1" is in the given integer array nums (list). Use the following two methods to solve:

• num2 in list, the return value is true, indicating that the second number is also in the array list list;
• nums.index(num2), find the index value of num2 in the array list, which is the position of the second number.

The code function is as follows:

class Solution:
    def twoSum(self, nums: List[int], target: int):
        lens = len(nums)
        j=-1
        for i in range(lens):
            if (target - nums[i]) in nums:
                if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):#If num2=num1, and there is only one occurrence in nums, it means that num1 itself is found.
                    continue
                else:
                    j = nums.index(target - nums[i],i+1) #index(x,i+1) is to find num2 from the sequence after num1                
                    break
        if j>0:
            return [i,j]
        else:
            return []

The execution passed, but it took a long time, 1048ms.
Improve the algorithm on the basis of the above method, thinking that the search of num2 does not need to search from nums every time, but only needs to search before or after the position of num1. But for convenience index here is chosen to look up from num1 position before:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        lens=len(nums)
        j=-1
        for i in range (1,lens):
            temp=nums[:i]
            if (target-nums[i]) in temp:
                j=nums.index(target-nums[i])
                break
        if j>=0:
            return [i,j]

The execution is passed, and the time-consuming is reduced by more than half to 444ms.

Algorithm Complexity Analysis

Time complexity: For each element, we try to find its corresponding target element by traversing the rest of the array, so the corresponding time complexity is O(n)*O(n);
The space complexity is: O(n).

Method 2: Sort + double pointer method

Here, first sort the array O(nlogn), and then use the double pointer method to traverse O(n) to get the result. In order to save the subscript information, another array is opened.
Time complexity O(nlogn), space complexity O(n)
code show as below:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp=nums.copy()
        temp.sort()
        i=0
        j=len(nums)-1
        while i<j:
            if (temp[i]+temp[j])>target:
                j=j-1
            elif (temp[i]+temp[j])<target:
                i=i+1
            else:
                break
        p=nums.index(temp[i])
        nums.pop(p)
        k=nums.index(temp[j])
        if k>=p:
            k=k+1
        return [p,k]

The execution is passed, and the usage time is 76ms, which greatly shortens the running time.

Method 3: hash method

Use the undered_map array to construct a map, and when traversing nums[i], check whether target-nums[i] exists in the hash table.
Time complexity O(n), space complexity O(n)
code show as below:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashset={}
        for i in range(len(nums)):
            if hashset.get(target-nums[i]) is not None :
                return [hashset.get(target-nums[i]),i]
            hashset[nums[i]]=i

The execution passed, and the running time was 76ms.