首页 > 代码库 > Leetcode | 3Sum

Leetcode | 3Sum

2024-07-03 16:11:36   225人阅读

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)

主要在去重方面走了弯路。思路同Two sum.

从num中取出一个数，就要把它的所有和为0的组合找出来。

找到一组之后，找下一组，i++,j--，但是要注意去重。

取出一个数的时候，就从它后面开始找其他两个数，因为在他之间的数已经找过了。 i = k + 1; 

确定范围之后，下一个k必须要忽略相同的数（Line 12) num[k] != num[k+1],k++。

 1     vector<vector<int> > threeSum(vector<int> &num) {
 2         vector<vector<int> > ret;
 3         if (num.size() < 3) return ret;
 4         
 5         vector<int> v;
 6         sort(num.begin(), num.end());
 7         
 8         for (int k = 0; k < num.size(); ++k) {
 9             // get num[k], search in [k + 1, n - 1]
10             int i = k + 1, j = num.size() - 1;
11             
12             // ignore duplicate num[k]
13             while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
14             
15             while (j > i) {
16                 int s = num[i] + num[j];
17 
18                 if (s == -num[k]) {
19                     v.push_back(num[i]);
20                     v.push_back(num[k]);
21                     v.push_back(num[j]);
22                     sort(v.begin(), v.end());
23                     ret.push_back(v);
24                     v.clear();
25                     
26                     // continue to find another match
27                     i++;
28                     while (i <= j && num[i] == num[i - 1]) i++;
29                     j--;
30                     while (j >= i && num[j] == num[j + 1]) j--;
31                 } else if (s > -num[k]) {
32                     j--;
33                 } else {
34                     i++;
35                 }
36             }
37         }
38         
39         return ret;
40     }

 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

和3 sum类似，就是在查找的时候，必须跟踪最小的差值。

 1 class Solution {
 2 public:
 3     int threeSumClosest(vector<int> &num, int target) {
 4         if (num.size() < 3) return INT_MAX;
 5         
 6         sort(num.begin(), num.end());
 7         int minDiff = INT_MAX, minSum = target;
 8         for (int k = 0; k < num.size(); ++k) {
 9             // get num[k], search in [k + 1, n - 1]
10             int i = k + 1, j = num.size() - 1;
11             
12             int t = target - num[k]; 
13             
14             while (j > i) {
15                 int s = num[i] + num[j];
16                 if (abs(s - t) < minDiff) {
17                     minDiff = abs(s - t);
18                     minSum = s + num[k];
19                 }
20                 if (s == t) {
21                     return target;
22                 } else if (s > t) {
23                     j--;
24                 } else {
25                     i++;
26                 }
27             }
28             
29             // ignore duplicate num[k]
30             while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
31         }
32         
33         return minSum;
34     }
35 };

 4Sum

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

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

3 sum类似，加了一层。

 1 class Solution {
 2 public:
 3     vector<vector<int> > fourSum(vector<int> &num, int target) {
 4         vector<vector<int> > ret;
 5         if (num.size() < 4) return ret;
 6         
 7         vector<int> v;
 8         sort(num.begin(), num.end());
 9         
10         for (int m = 0; m < num.size(); ++m) {
11             for (int k = m + 1; k < num.size(); ++k) {
12                 // get num[k], search in [k + 1, n - 1]
13                 int i = k + 1, j = num.size() - 1;
14                 int t = target - num[m] - num[k];
15                 // ignore duplicate num[k]
16                 while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
17                 
18                 while (j > i) {
19                     int s = num[i] + num[j];
20     
21                     if (s == t) {
22                         v.push_back(num[m]);
23                         v.push_back(num[k]);
24                         v.push_back(num[i]);
25                         v.push_back(num[j]);
26                         sort(v.begin(), v.end());
27                         ret.push_back(v);
28                         v.clear();
29                         
30                         // continue to find another match
31                         i++;
32                         while (i <= j && num[i] == num[i - 1]) i++;
33                         j--;
34                         while (j >= i && num[j] == num[j + 1]) j--;
35                     } else if (s > t) {
36                         j--;
37                     } else {
38                         i++;
39                     }
40                 }
41             }
42             while (m < num.size() - 1 && num[m] == num[m + 1]) m++;
43         }
44         return ret;
45     }
46 };

 4 sum有O(n^2)的解法，leetcode的discuss后面有。明天再写。


联系
我们