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 n n, If the array is n u l l null null Or the array length is less than 3 3 3, return [ ] [] [].
  2. Sort the array .
  3. Traversing the sorted array :
    1. if n u m s [ i ] > 0 nums[i]>0 nums[i]>0: Because it's sorted , So there can't be three numbers that add up to 0 0 0, Direct return .
    2. For repeating elements : skip , Avoid duplicate solutions
    3. Left pointer L = i + 1 L=i+1 L=i+1, Right pointer R = n − 1 R=n-1 R=n1, When L < R L<R L<R when , Execute loop :
      • When n u m s [ i ] + n u m s [ L ] + n u m s [ R ] = = 0 nums[i]+nums[L]+nums[R]==0 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 L,R L,R Move to the next position , Looking for new solutions
      • If sum is greater than 0 0 0, explain n u m s [ R ] nums[R] nums[R] Too big , R R R Move left
      • If sum is less than 0 0 0, explain n u m s [ L ] nums[L] nums[L] Too small , L L 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;
}
};
Please bring the original link to reprint ,thank
Similar articles

2021-10-14