首页 > 代码库 > 【leetcode】3Sum

【leetcode】3Sum

2024-08-10 09:50:05   218人阅读

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)
 
先对数组进行排序，从头开始扫描，扫描的数作为固定的数。
a=num[i];
 
当固定了一个数以后，
选取b=num[i+1]=num[j]
选取c=num[n-1]=num[k]
 
 
若a+b+c=0
则找到了一个a，b，c，记录下来，j++,k--继续扫描
若a+b+c<0
则j++
若a+b+c>0
则k--
 
 
要注意去重的问题：
1.若num[i]=num[i-1]，则跳过
2.若num[j]=num[j-1]，则跳过
3.若num[k]=num[k+1]，则跳过
 
 
 1 class Solution { 2 public: 3     vector<vector<int> > threeSum(vector<int> &num) { 4         5         int n=num.size(); 6         sort(num.begin(),num.end()); 7         8         int i,j,k; 9         int a,b,c;10         vector<vector<int> > result;11        12         for(i=0;i<n-2;i++)13         {14             j=i+1;15             k=n-1;16            17             while(j<k)18             {19                 a=num[i];20                 if(i>0&&num[i]==num[i-1])21                 {22                     break;23                 }24                 b=num[j];25                 if(j>i+1&&num[j]==num[j-1])26                 {27                     j++;28                     continue;29                 }30                31                 c=num[k];32                 if(k<n-1&&num[k]==num[k+1])33                 {34                     k--;35                     continue;36                 }37                38                 if(a+b+c==0)39                 {40                     vector<int> tmp(3);41                     tmp[0]=a;42                     tmp[1]=b;43                     tmp[2]=c;44                     result.push_back(tmp);45                     j++;46                     k--;47                 }48                 else if(a+b+c<0)49                 {50                     j++;51                 }52                 else if(a+b+c>0)53                 {54                     k--;55                 }56             }57         }58        59         return result;60        61     }62 };63

 

【leetcode】3Sum


联系
我们