Sum of two numbers and three numbers

1. 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 .

Example 1：
Input ：nums = [2,3,5,7,11,13], target = 12
Output ：[2,3]
explain ： because nums[2] + nums[3] == 12 , return [2, 3] .

1. Two loops

The most direct solution is the combination of numbers in pairs of arrays , Then find the sum , This directly uses two loops , Because it's a combination of two , And there is no need to repeat , therefore j Directly from i Then start selecting

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        for i in range(n):
            for j in range(i+1,n):
                if nums[i] + nums[j] == target:
                    return i,j

2. Sort + Double pointer

If the location is not considered , Directly return two data , We also have a double pointer method . The idea of double pointer is also very simple , We first sort the array in ascending order , Then the two pointers point to the head and tail respectively

1. if nums[L]+nums[R]>tartet : R-=1
2. if nums[L]+nums[R]<tartet : L+=1

2	3	5	7	11	13
L					R

2+13>12, At this time, the sum of the two numbers is greater than the target value , We move the right pointer , This will make the sum of two numbers smaller

2	3	5	7	11	13
L				R

2+11>12, At this time, the sum of the two numbers is greater than the target value , We move the right pointer , This will make the sum of two numbers smaller

2	3	5	7	11	13
L			R

2+7<12, At this time, the sum of the two numbers is less than the target value , We move the left pointer , In this way, the sum of two numbers can be made larger

2	3	5	7	11	13
	L		R

3+7<12, At this time, the sum of the two numbers is less than the target value , We move the left pointer , In this way, the sum of two numbers can be made larger

2	3	5	7	11	13
		L	R

5+7=12, Found a set of data .
You can see , The first step of double pointer is to sort the array , This will directly disrupt the order of the original array , So even if you get satisfied targe Two data of , It also needs to pass index Function mapping back

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        arr = zip(nums,range(len(nums)))
        arr = sorted(arr, key=lambda x:x[0])
        l,r=0,len(nums)-1
        while l < r:
            print(l,r)
            if arr[l][0]+arr[r][0]>target:r-=1
            elif arr[l][0]+arr[r][0]<target:l+=1
            else: return arr[l][1],arr[r][1]

3. hash

Then I looked at another solution , It's also very clever , Use hash Table to store data . For a number in the array nums[i], We need to find a number that satisfies target-nums[i], That is to find whether there is a number in the original array nums[j]=target-nums[i], This turns into a search problem .

nums[i]	2	7	11	5
nums[j]=target-nums[i]	9-2=7	9-7=2	9-11=-2	9-5=4

Sum of three numbers

Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .
Be careful ： Answer cannot contain duplicate triples .

Example 1：
Input ：nums = [-1,0,1,2,-1,-4]
Output ：[[-1,-1,2],[-1,0,1]]

1. Three levels of circulation （ Violent algorithms are fearless ）

The most direct idea is three levels for Loop to solve the combination of three arrays . However, during debugging, it is found that the same elements will appear in the array , This will lead to repeated results , For example 1, Due to repetition -1, Therefore, repetition also occurs in the process of circulation , That is the first one. -1 And the second -1 Can and 0,1 The combination meets the result , So twice .

[[-1,0,1],[-1,2,-1],[0,1,-1]]

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.append([nums[i],nums[j],nums[k]])
        return res

We can deal with the repetition problem by sorting the array , You can see there are two -1, I marked it in red and green respectively .

1. first -1 Will be with 0,1,2 Are combined , the second -1 Will also be with 0,1,2 Are combined , This will lead to repeated results , So we only need to choose one -1 That's all right.
2. Which one to choose -1 Well ？ Obviously, you should choose the first -1, Because the first one -1 You can also work with the second -1 Are combined , first -1 The combination number of has included the second -1 The combination number of
   

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        n = len(nums)
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:continue #  Keep the first 
            for j in range(i+1,n):
                for k in range(j+1,n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        res.append([nums[i],nums[j],nums[k]])
        return res

There will still be repeated problems , for instance nums=[-5,0,2,2,3,3], It's going to happen twice 2,3 Result , Therefore, the internal cycle still needs to be judged , But it's hard to get rid of the weight through circulation . You can use double pointers to remove duplicates

2. Sort + Double pointer

The array is already in order , When we solved the sum of two numbers , The double pointer method is also used . But now we need to consider the problem of weight removal . After determining the first element , We use two pointers to point to the head and tail respectively

1. if nums[F] + nums[L]+nums[R]>0 : R-=1
2. if nums[F] + nums[L]+nums[R]<0 : L+=1

-6	-5	1	2	2	3	3	4
First	L						R
First		L					R
First			L				R

Now we have found a set of solutions , But the problem requires that we solve all the feasible solutions , So you need to continue moving the double pointer . But this case It can be found that if we move the pointer, we will still get the repeated solution , So it needs to be removed , namely

while L < R and nums[L]==nums[L+1]:L+=1
while L < R and nums[R]==nums[R-1]:R-=1

emphasis ： Cycle until you find the next different number

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        n = len(nums)
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:continue
            l,r=i+1,n-1
            while l < r:
                if nums[l]+nums[r]>-nums[i]:
                    r -= 1
                elif nums[l]+nums[r]<-nums[i]:
                    l += 1
                else:
                    res.append([nums[l],nums[r],nums[i]])
                    while l < r and nums[l] == nums[l+1]:l += 1
                    while l < r and nums[r] == nums[r-1]:r -= 1
                    l += 1
                    r -= 1
        return res

Cyclic search

It's obviously a two-layer loop. Why do you only need to loop once after changing to double pointers ？ This is because after sorting , Double pointers can filter many operations that do not need loops .
Take a specific case, For example, find the sum of two numbers , among nums = [2,3,5,7,11,13], target = 12,

for i in range(n):
	for j in range(i+1,n):
		print(nums[i],nums[j])
		if nums[i]+nums[j] == target:
			res.append(nums[i],nums[j])

If we first determine a number 2, Followed by 2,3,5,7,11,13 Are combined , When we combine to 11 When 2+11>13, Then we need to go with bigger 13 To group , Obviously not needed , So we can add a judgment directly , Skip the following numbers

for i in range(n):
	for j in range(i+1,n):
		print(nums[i],nums[j])
		if nums[i]+nums[j] == target:
			res.append(nums[i],nums[j])
		elif nums[i]+nums[j] > target:
			break

Now it's time to find an interesting point ,2 and 11 Combination greater than 12, therefore 2 No need to follow 13 Combine , So the first cycle is 3, I need to follow 11 and 13 Combination , Definitely not needed , in other words , The end of our second level loop is not always n, It can be pushed forward

r = n
for i in range(n):
	for j in range(i+1,r):
		print(nums[i],nums[j])
		if nums[i]+nums[j] == target:
			res.append(nums[i],nums[j])
		elif nums[i]+nums[j] > target:
			r = j
			break