Sum the two numbers to find the target value

subject ： 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 .
Their thinking
Find the sum of two numbers , Using fast and slow pointers , When two pointers When the extracted function value is added to the target value , Meet the conditions

The first solution ： Violence enumeration

This solution is the easiest to come up with , But the memory consumption is too large

class Solution(object):
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        L = []
        n = len(nums)
        for i in range(n-1):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    L.append(i)
                    L.append(j)
                j = j + 1
            i = i + 1
        return L

double for loop ： Double pointers for convenient summation
Time complexity ：n*n, Spatial complexity , Introduced a new array , by n

Code transformation

class Solution(object):
    def twoSum(self, nums, target):
        #  Method 1.  Convenient array , Enumeration , Time and space consumption is huge 
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

Time complexity ：n*n, Spatial complexity ：1

Method 2 ： Hashtable

Function method ：
The method of all key value pairs in the convenience dictionary ：

for...in... #  Loop statements to facilitate all key value pairs 

==enumerate()== Function instructions ：

• enumerate() yes python Built in functions for
• enumerate In the dictionary is enumeration 、 List means
• For an iterative （iterable）/ Traversable objects （ As listing 、 character string ）,enumerate Make it into an index sequence , Use it to get both index and value
• enumerate It's mostly used in for Count in the loop

#  for example ： Output the subscript corresponding to each character in the list 
listx = [" this ", " yes ", " One ", " test "]
for i in range(len(listx)):
	print i, listx[i]
# enumerate() Use of functions 
listx = [" this ", " yes ", " One ", " test "]
for index, item in enumerate(listx):
    print index, item

The output is as follows :

Therefore, this question can be modified by hash table ：
Thought analysis ：
The time of searching in the list can be reduced through hash table

class Solution(object):
    def twoSum(self, nums, target):
        #  Method 2 ： Hashtable ,set No, index,dict No, add attribute 
        visited = dict()
        for i,num in enumerate(nums):
            if (target-num) in visited:
                return (visited[target-num], i)
            visited[nums[i]] = i
        return []

error analysis ：
- Use set, however set() Cannot return subscript , Therefore adopt dict()
Time complexity ：o(N), Spatial complexity o(1)