Leecode15. Sum of three numbers -- leecode100 hot questions series

I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression

The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ！ Leaving a message. ！

Portal ——>Leecode Big factory hot topic 100 Tao series problem solution

Problem description

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

Tips ：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

The core idea

Sort + Double pointer + Fixed elimination method

practice

1. Special judgement , For array length $n$, If the array is $null$ Or the array length is less than $3$, return $[]$.
2. Sort the array .
3. Traversing the sorted array ：
   1. if $nums[i]>0$： Because it's sorted , So there can't be three numbers that add up to $0$, Direct return .
   2. For repeating elements ： skip , Avoid duplicate solutions
   3. Left pointer $L=i+1$, Right pointer $R=n-1$, When $L<R$ when , Execute loop ：
      • When $nums[i]+nums[L]+nums[R]==0$, Execute loop , Judge whether the left and right bounds are repeated with the next position , Remove duplicate solutions . At the same time $L,R$ Move to the next position , Looking for new solutions
      • If sum is greater than $0$, explain $nums[R]$ Too big ,$R$ Move left
      • If sum is less than $0$, explain $nums[L]$ Too small ,$L$ Move right

Code

class Solution {

public:
vector<vector<int>> threeSum(vector<int>& nums) {

vector<vector<int>> res;
set<vector<int>> s;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) {

// duplicate removal 
if(i > 0 && nums[i] == nums[i-1]) continue;
// If > 0 Represents that the following are greater than 0
if(nums[i] > 0) break;
int l = i + 1, r = nums.size()-1;
while(l < r) {

int t = nums[i] + nums[l] + nums[r];
if(t == 0) {

res.push_back({
nums[i], nums[l], nums[r]});
while(l < r && nums[l] == nums[l+1]) l++;
while(l < r && nums[r] == nums[r-1]) r--;
r--; l++;
} else if(t > 0) {

r--;
} else if(t < 0) {

l++;
}
}
}
return res;
}
};