[LeetCode] 015. 3Sum (Medium) (C++/Java/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

015.3Sum (Medium)链接：

题目：https://oj.leetcode.com/problems/3sum/代码(github)：https://github.com/illuz/leetcode

题意：

在给定数列中找出三个数，使和为 0。

分析：

先排序，再左右夹逼，复杂度 O(n*n)。N-sum 的题目都可以用夹逼做，复杂度可以降一维。

这题数据更新后卡得很紧， C++ 不能全部加完再用 STL 的 erase 和 unique 去重，，要一边判断一边加。

代码：

C++:

class Solution {public:vector<vector<int> > threeSum(vector<int> &num) {vector<vector<int> > ret;int len = num.size();int tar = 0;if (len <= 2)return ret;sort(num.begin(), num.end());for (int i = 0; i <= len – 3; i++) {// first number : num[i]int j = i + 1;// second numberint k = len – 1;// third numberwhile (j < k) {if (num[i] + num[j] + num[k] < tar) {++j;} else if (num[i] + num[j] + num[k] > tar) {–k;} else {ret.push_back({ num[i], num[j], num[k] });++j;–k;// folowing 3 while can avoid the duplicationswhile (j < k && num[j] == num[j – 1])++j;while (j < k && num[k] == num[k + 1])–k;}}while (i <= len – 3 && num[i] == num[i + 1])++i;}// sort and unique will cost a lot of time and course TLE// sort(ret.begin(), ret.end());// ret.erase(unique(ret.begin(), ret.end()), ret.end());return ret;}};

Java:

public class Solution {public List<List<Integer>> threeSum(int[] num) {List<List<Integer>> ret = new ArrayList<List<Integer>>();int len = num.length, tar = 0;if (len <= 2)return ret;Arrays.sort(num);for (int i = 0; i <= len – 3; i++) {// first number : num[i]int j = i + 1;// second numberint k = len – 1;// third numberwhile (j < k) {if (num[i] + num[j] + num[k] < tar) {++j;} else if (num[i] + num[j] + num[k] > tar) {–k;} else {ret.add(Arrays.asList(num[i], num[j], num[k]));++j;–k;// folowing 3 while can avoid the duplicationswhile (j < k && num[j] == num[j – 1])++j;while (j < k && num[k] == num[k + 1])–k;}}while (i <= len – 3 && num[i] == num[i + 1])++i;}return ret;}}

Python:

class Solution:# @return a list of lists of length 3, [[val1,val2,val3]]def threeSum(self, num):if len(num) <= 2:return []ret = []tar = 0num.sort()i = 0while i < len(num) – 2:j = i + 1k = len(num) – 1while j < k:if num[i] + num[j] + num[k] < tar:j += 1elif num[i] + num[j] + num[k] > tar:k -= 1else:ret.append([num[i], num[j], num[k]])j += 1k -= 1# folowing 3 while can avoid the duplicationswhile j < k and num[j] == num[j – 1]:j += 1while j < k and num[k] == num[k + 1]:k -= 1while i < len(num) – 2 and num[i] == num[i + 1]:i += 1i += 1return ret

“人无完人金无足赤”，只要是人就不会是完美的，