leetCode The first 1 topic Sum of two numbers
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 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
The first method is violence enumeration
Place two pointers first , The second pointer is placed after the first , Then move the second pointer one by one until the traversal is complete , Then move the first pointer one bit , The second pointer is placed after the first pointer , repeat .
# python3
class Solution:
def twoSum(self, nums: [int], target: int) -> [int]:
result = []
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j] == target:
result.append(i)
result.append(j)
return result
return result
After submission, it was found that the effect of the violence law was not very good , It should be optimized 
In the law of violence , Because of the cycle , As a result, we are constantly repeating the scanned values , This wastes a lot of time .
So we can introduce hash map Used to store subscripts and corresponding values （ stay python Can be implemented with a dictionary hash map The function of ）
First set up a pointer to the first element , here hash map It should be an empty table
Point first 4, The target value is 20, We're going to hash map Look for it 16 This value , But I didn't find （ This is an empty table ）, If you don't find it, just 4 Put this element into hash map in , Then the pointer moves back .
When the pointer points to 7 This number of hours , stay hash map You can find 13 This value , So we use hash map in 13 The corresponding subscript and the subscript of the pointer return
# python3
class Solution:
def twoSum(self, nums: [int], target: int) -> [int]:
hash_map = {
} # establish hash map, Use a dictionary to realize
result = []
for i in range(len(nums)):
index = hash_map.get(target-nums[i])
if None != index : # hash map There is , Then record the subscript
result.append(index)
result.append(i)
break
else: # hash map There is no corresponding element in , The new element is stored in hash map
hash_map[nums[i]] = i
return result
In the whole process of execution , We are only right nums I scanned it again , So it is a linear time complexity , by O(m)
Memory usage has increased a lot , But the time is much shorter .
