首页 > 代码库 > leetcode. 3sum

leetcode. 3sum

2024-08-05 13:24:53   215人阅读

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)

1、先对数组进行排序，时间复杂度O(nlbn)
2、下表i指向数组首部，则题目可以转为2sum问题：即对数组num[i+1, num.size - 1], 求2sum的target == -num[i]

tips：
　　注意重复结果
 1     vector<vector<int> > threeSum(vector<int> &num)    2     {   3         int i = 0, j = 0, k = 0;   4         int target = 0;   5         vector<int> t(3);   6         vector<vector<int> > vt;   7         if (num.size() < 3) 8             return vt; 9             10         sort(num.begin(), num.end());  11         while (i < num.size() - 2)  12         {  13             target = 0 - num[i];  14             t[0] = num[i];15             j = i + 1;16             k = num.size() - 1;17             while (j < k)  18             {  19                 if (num[j] + num[k] == target)  20                 {  21                     t[1] = num[j++];  22                     t[2] = num[k--];  23                     vt.push_back(t);  24                     while (j < k && num[j] == num[j-1])  25                         j++;  26                     while (j < k && num[k] == num[k+1])  27                         k--;  28                 }  29                 else if (num[j] + num[k] < target)  30                     j++;  31                 else  32                     k--;  33             }  34             i++;  35             while ((i < num.size() - 2) && num[i] == num[i-1])  36                 i++;  37         }38         39         return vt;  40     }

 

3sum closest 只需找到最接近的即可：

 1 int threeSumClosest(vector<int> &num, int target)  2     { 3         int i = 0, j = 0, k = 0;   4         int min = 0x7fffffff, delta = 0, closest = 0;   5         if (num.size() < 3) 6             return 0; 7              8         sort(num.begin(), num.end());   9         for (i = 0; i < num.size() - 2; i++)  10         {  11             j = i + 1;12             k = num.size() - 1;13             while (j < k)  14             {15                 delta = num[i] + num[j] + num[k] - target;16                 if (min > abs(delta))17                 {18                     min = abs(delta); 19                     closest = num[i] + num[j] + num[k];20                 }21                 22                 if (delta < 0)23                     j++;24                 else if (delta > 0)25                     k--;26                 else27                     j++, k--;28             }      29         }30         31         return closest;32     }

 

leetcode. 3sum


联系
我们