首页 > 代码库 > leetcode. 3sum
leetcode. 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)
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。