Leetcode-15- sum of three numbers (medium)

15. Sum of three numbers （ secondary ）

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]]

Example 2：

 Input ：nums = []
 Output ：[]

Example 3：

 Input ：nums = [0]
 Output ：[]

Ideas ： Sort + Double pointer

• Sort ： First set the given nums Sort , The complexity is O(NlogN).

• The idea of double finger needling ： Fix 3 The leftmost pointer （ Minimum ） A pointer to a number k, Double pointer i,j Set in array index (k, len(nums)) Both ends , Move alternately to the middle through the double pointers , Record for each fixed pointer k All of them are satisfied nums[k] + nums[i] + nums[j] == 0 Of i,j Combine ：

  • When nums[k] > 0 It's direct break Jump out of ： because nums[j] >= nums[i] >= nums[k] > 0, namely 3 Both numbers are greater than 0 , Fix the pointer here k It's impossible to find the result after that .
  • When k > 0 And nums[k] == nums[k - 1] Skip this element when nums[k]： Because it has been nums[k - 1] All combinations of are added to the results , This double pointer search will only get repeated combinations .
  • i,j Set in array index (k, len(nums)) Both ends , When i < j Time cycle calculation s = nums[k] + nums[i] + nums[j], And perform double pointer movement according to the following rules ：
    • When s < 0 when ,i += 1 And skip all repeated nums[i];
    • When s > 0 when ,j -= 1 And skip all repeated nums[j];
    • When s == 0 when , Record combination [k, i, j] to res, perform i += 1 and j -= 1 And skip all repeated nums[i] and nums[j], Prevent duplicate combinations from being recorded .

• Complexity analysis ：

  • Time complexity O(N^2)： Where the fixed pointer k Cycle complexity O(N), Double pointer i,j Complexity O(N).
  • Spatial complexity O(1)： Pointers use extra space of constant size .

（1）C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp(3);
        int m = nums.size();
        sort(nums.begin(),nums.end());
        for(int k=0;k<m-2;k++){
            if(nums[k]>0) break;
            if(k>0 && nums[k]==nums[k-1])  continue;
            int i=k+1 , j=m-1;
            while(i<j){
                int s =nums[k]+nums[i]+nums[j];
                if(s==0){
                    temp[0]=nums[k];
                    temp[1]=nums[i];
                    temp[2]=nums[j];
                    res.emplace_back(temp);
                    i++;
                    j--;
                    while(i<j && nums[i]==nums[i-1]) i++;
                    while(i<j && nums[j]==nums[j+1]) j--;
                }
                else if(s>0){
                    j--;
                    while(i<j && nums[j]==nums[j+1]) j--;
                }
                else{
                    i++;
                    while(i<j && nums[i]==nums[i-1]) i++;
                }
                
            }
        }
        return res;
    }
};

（2）python

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