Force deduction brush question (2): sum of three numbers

1 Problem description

Given an inclusion n Array of integers nums, Judge nums Whether there is 3 Elements $ a、b、c$, bring $a+b+c=0$.

Find all triples that meet the conditions and are not repeated .

Be careful ： Answer cannot contain duplicate triples .

for example , Given array $nums=[-1,0,1,2,-1,-4]$, The set of triples satisfying the requirement is $[[-1,0,1],[-1,-1,2]]$.

The requirements of the topic are as follows .

1. find 3 The sum of the numbers equals 0, instead of “ Sum of two numbers ” The indefinite value in target, Therefore, this topic is a special case .
2. The title requires that the number itself be returned , Not the index value .
3. There are multiple answers to this question , Different from the previous question , This question requires that all possible answers be returned .
4. Answer cannot contain duplicate triples , So we need to consider weight removal .

2 Problem analysis

Because this problem requires no longer to return the index value , So sort first , Then the idea of using double pointers is feasible .

The specific algorithm is to sort the original array first , Then a layer of loop fixes an element , Inside the loop, use double pointers to find the remaining two elements , Special attention should be paid here to the weight removal .

3 python Realization

Remember what Qian Xuesen said , Everything should be grasped from the whole .

The solution to this problem , By fixing $i$, Go looking for $l$,$r$.

The length of the array is $n$, The position of the first element is $0$, The last one is $n-1$,

class Solution2:
    def threeSum(self, nums):
        n = len(nums)
        nums.sort()     #  Yes  nums  Sort the array in ascending order 
        res = []        #  Define a list of controls （ Array ）
        
        for i in range(n-2):
            if i > 0 and nums[i] == nums[i-1]:   #  This part is to remove the duplicate part 
                continue
            l = i + 1
            r = n - 1
            while (l < r):
                if (nums[i] + nums[l] + nums[r] < 0):
                    l += 1
                elif (nums[i] + nums[l] + nums[r] > 0):
                    r -= 1
                else:   
                    res.append([nums[i],nums[l],nums[r]])
                    while (l < r and nums[l] == nums[l + 1]): #  To remove duplicate parts  
                        l += 1                                #  Just repeat ,l The pointer moves all the way to the right 
                    while (l < r and nums[r] == nums[r - 1]): #  To remove duplicate parts 
                        r -= 1                                #  Just repeat ,r The pointer keeps moving left 
                    l += 1
                    r -= 1
        return res
        
fu2 = Solution2()

nums2 = [-1,0,1,2,-1,-4]
print(fu2.threeSum(nums2))
nums2.sort()
print(nums2)

4 Step by step analysis