Force deduction question (1) -- sum of two numbers

Sum of two numbers

Topic content

Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

Example

Example 1：

 Input ：nums = [2,7,11,15], target = 9
 Output ：[0,1]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .

Example 2：

 Input ：nums = [3,2,4], target = 6
 Output ：[1,2]

Example 3：

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Tips ：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
* There will only be one valid answer *

 Advanced ： You can come up with a time complexity less than  O(n2)  The algorithm of ？

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/two-sum

Answer key

Answer 1 ： Double cycle violent solution

The first reaction to this problem is the double loop solution .

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(0, length):
            for j in range(i+1, length): #  Because there must be an answer , There is no need to consider the boundary problem of the second layer cycle , namely  i+1  It must not equal  length
                if nums[i] + nums[j] == target:
                    return [i, j]

Obviously , Because it is a double cycle violent solution , So it takes a long time to pass on the buckle , Probably 3344 ms

Explanation 2 ： Advanced version of double cycle solution

The first kind of double cycle of problem solving is the double cycle without brain , Don't judge whether it is necessary to double cycle —— For example, whether there is a number and the number of the first layer of the cycle add up to our target number .
So what we need to do in the advanced version is to add a layer of judgment before the second layer of circulation to judge whether it is necessary to carry out the second layer of circulation .

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(0, length):
            if (target - nums[i]) in nums: #  Determine whether it is necessary to carry out the second layer of circulation 
                for j in range(i+1, length):
                    if nums[j] + nums[i] == target:
                        return [i, j]

The time of force buckle passing is about 728 ms

Answer 3 ： utilize python function index

Direct search without double loop target - nums[i] The position of the number in the list

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0, len(nums)):
            num1 = target - nums[i]
            if num1 in nums: #  Judge  target - nums[i]  Is it in the list 
                j = nums.index(num1)
                if j != i: #  Judge whether the position of the positioned number is consistent with that of the first cycle 
                    return [i, j]

The time of force buckle passing is about 724 ms

Solution 4 ： Dictionary simulation hash table

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {
    } #  Dictionaries  key  Value record number ,value  Record subscripts , Because there is only one answer , Don't consider the problem that the coverage caused by the same number leads to incomplete answers 

        for i in range(0, len(nums)):
            num1 = target - nums[i]
            if num1 in dic: #  Determine whether the number exists in   In the dictionary 
                return [dic.get(num1), i]
            dic[nums[i]] = i #  Record numbers and subscripts 

The time of force buckle passing is about 40 ms