ThreeSum [source code]
public class ThreeSum {
static
/******************************************************************************/
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length < 3)
return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1]) //mind the order of premature exits
continue;
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
if (nums[i] + nums[lo] + nums[hi] == 0) {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1])
lo++;
while (lo < hi && nums[hi] == nums[hi - 1])
hi--;
lo++;
hi--;
} else if (nums[i] + nums[lo] + nums[hi] < 0) {
lo++;
} else hi--;
}
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
ThreeSum.Solution tester = new ThreeSum.Solution();
}
}
拿到题目的第一个想法就是很简单的一个, 直接用2sum的方法来做; 但是有一个小问题, 怎么保证没有重复? 想了一下或许这个题目反过来也可以用DFS来做? 不过那个的复杂度就太高了; 用2sum来做的话顶多N^2; 另外这个问题的复杂度注定是在N^2周边了, 所以或许可以干脆先一个sort降低难度? 反正也无关轻重了;
先不考虑重复的问题了, 直接先2sum来做, 做完再看怎么加上这一个feature, relaxation baby;
想了一下还是挺没有思路的, 直接看答案了;
最后按照答案写了一个出来, 速度是75ms (92%), N^2的解;
TODO: 这个题目如果是N^3的解怎么做? discussion没有找到可以参考的;
这个是discussion最优解:
The idea is to sort an input array and then run through all indices of a possible first element of a triplet. For each possible first element we make a standard bi-directional 2Sum sweep of the remaining part of the array. Also we want to skip equal elements to avoid duplicates in the answer without making a set or smth like that.
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi--;
lo++; hi--;
} else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
注意他这里的Arrays.asList(num[i], num[lo], num[hi])的用法, 原来我以前的用法一直是错的, 这里根本不需要加大括号, 直接就把几个全都放在小括号里面就行了? 这个倒是没想到, 而且也有点难以理解到底是怎么实现的, JAVA可以实现不定长度的参数表吗?
这里可以看到, 原来这个remove duplicate才是这个问题的核心难度所在, 不然就是2sum问题的一个最简单的扩展, 这个也显得未免有些trivial了;
所以他这里的意思就是说, 这个题目正常的remove duplicate的思路其实就是用set, 这个很常见; 当然具体的怎么做我还不太清楚了比如list和list之间可以通过set的功能完成一个自动消除吗? 或者说我们一开始保存的最好是set? 这样可以无视list的order?
另外他这里果然还是先sort降低难度了, 这个可能也算是我自己也想到了的一个点; sort在这个问题中达到降低难度以及加速度的一个原因是, 这里你只需要对整个的大array做一个sort就行了, 而不是每一个inner循环要做一个sort;
这里他实现remove duplicate的思路也不能说没有见过, 就是一个impose order的思路, 只不过具体的做法上不是那么直接; 如果我说让你找一个pair, 然后不能有duplicate(简单升级, 要你找的是triplet, then why don't you start from pairs? (注意, 这个思路指的是你寻找的是某一个具体问题的答案, 比如是remove duplicate方案的解决办法, 这个时候你用这个简单类比的思路可能有帮助; 但是直接很粗暴的直接上来就整个问题都简化来寻找类比, 有时候并不见得有效)), 你会怎么做呢? 常见的做法就是比如i和j, 那么保证j始终在i的后面, 也就是impose the order of i < j 就行了; 这里的triplet的情形也是一样的;
感觉remove duplicate和impose order这两个概念其实我并没有理解的很好; 比如来说, 我直到这题为止, 我都没有意识到impose order这个概念只适用于, 比如pair这种, 至少有两个element的东西的remove duplicate;
注意他这里有一个有趣的操作, 每当找到一个triplet之后:
- 首先, 我们肯定不能直接就立刻return, 你自己分析一下给的这个例子就知道了, 我们要找到的是所有的triplet, 所以虽然hit了一个, 但是我们还是要继续;
- 我们把lo和hi都左右移动, 直到移动到两个的值都不同于当前triplet给他们对应的取值; 注意这里他做的是两个都移动, 其实移动一个也可以了, 但是移动两个也一样, 而且节省一点时间; 事实上, 假如我们只移动lo, 那么下一个iteration, 我们就会发现sum过大(lo现在在the next value that is different than the previous hit lo, which is also larger than that), 然后我们就会想要想做移动hi, 最后得到的效果是一样的;
- 这个处理跟大循环的body外面wrap起来的那一层if的header上面, 要求判断i必须是某一个value的第一个取值, 是对应的; 比如
-1,-1,5,2这样的, 可能没有影响, 比如你i等于0的时候扫了一遍, 找到一个hit, 然后你i等于1的时候又扫了一遍, 没有hit, 这个是无所谓的, 但是假如是-1,-1,-1,5,2这样的, 就有区别了, 你在i等于0和1的位置将会找到两个一样的hit; 这两个措施必须共同采用才能保证最终没有duplicate;
- 这个处理跟大循环的body外面wrap起来的那一层if的header上面, 要求判断i必须是某一个value的第一个取值, 是对应的; 比如
底下有人尝试这样优化这个算法:
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
List<List<Integer>> res = new LinkedList<>();
for (int i = 0; i < num.length-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int lo = i+1, hi = num.length-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
res.add(Arrays.asList(num[i], num[lo], num[hi]));
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi--;
lo++; hi--;
} else if (num[lo] + num[hi] < sum) {
// improve: skip duplicates
while (lo < hi && num[lo] == num[lo+1]) lo++;
lo++;
} else {
// improve: skip duplicates
while (lo < hi && num[hi] == num[hi-1]) hi--;
hi--;
}
}
}
}
return res;
}
但是也有人认为这个其实并没有作用; 我也感觉其实是没有什么区别的;
这个是另外一个人写出来的一个类似的简短的算法:
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if(nums.length < 3) return result;
Arrays.sort(nums);
int i = 0;
while(i < nums.length - 2) {
if(nums[i] > 0) break;
int j = i + 1;
int k = nums.length - 1;
while(j < k) {
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k]));
if(sum <= 0) while(nums[j] == nums[++j] && j < k);
if(sum >= 0) while(nums[k--] == nums[k] && j < k);
}
while(nums[i] == nums[++i] && i < nums.length - 2);
}
return result;
}
}
注意他这里简化的更厉害, 他内循环的body用的是if chain而不是if else结构, 用来避免code duplicate; 不过这个代码的作者之后自己也说了这个代码其实就是写的玩玩, 他不认为这样的写法实际上对复杂度有任何的提升;
不过能够想到这样的简化还是有意思的; 平时自己学习的时候可以稍微看看, for fun, 但是真正面试的时候当然还是不用纠结这种小的噱头型的技巧;
另外他这把两个remove duplicate的措施写成了相似的形式, 在内循环里面有跳子操作, 然后内循环结束之后, 外循环以内, 立刻继续一个跳子操作; 其实与之前的做法达到的效果是类似的, 不过或许方便理解一些?
另外, 学习他这里跳子的算法: 或者是相邻判断的具体写法:
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi--;
我们在计算机编程的时候, 我们每一个指针/变量一次只能针对一个entry/value, 但是我们这里要做的是相邻判断, 也就是关于pair的判断, 那么怎么办呢? 最直接的做法其实就是只拿着一个指针, 然后判断(一个固定方向上的)另外一个指针; 比如我们要从左到右判断, 那么我们iterate var的这个变量, 应该是pair当中的左边还是右边呢?
事实上, 从效果上来说好像没有太大的区别? 不过一般来说, loop var好像用落后的指针比较多, 比如这里, lo扫描的是从左到右的方向, 所以相邻pair的左边就落后于右端点; 所以这里的lo判断的就是pair的左边; 这个也有点类似于之前关于伸脚算法的思路, 不过其实我目前还没有想到什么特别的实际效果;
一个有效的优化是:
A trick to improve performance: once nums[i] > 0, then break.
Since the nums is sorted, if first number is bigger than 0, it is impossible to have a sum of 0.
这个还是很聪明的, 有点类似branch&bound的思路; 也有人说这个加pruning. 好像是对的, branch&bound好像是optimization里面的概念, 而prune本身就是单纯的很general的reduce search space的意思;
我自己想的时候想到一个思路, 是否可以用一个visited flag的思路来避免duplicate? 当然这个visited实现方式也很简单, 一个assoc array就行了; 但是这个方法真的可以避免duplicate吗? 这个问题的duplicate难以处理还是因为不同的index可能有相同的value, 所以就算是你sort之后, 相邻的一些位置还是会有相同的值; 而visited flag的问题在于, 标记的其实是针对index, 而不是value, 所以感觉这个思路其实无法真正做到最后的remove duplicate.
当你思考和讨论remove duplicate的时候, 你脑子里不能只有"duplicate"这一个词语而已, 你要理解我们谈论的究竟是什么duplicate(甚至可以借用脑子里例子的帮助). 比如这个问题本身, 就有好几种意义的duplicate: array的entry本身之间就有duplicate, 最后我们要返回的结果之间(triplet之间, 或者说list之间)也有duplicate;
这个帖子里面有关于优于N^2的解法的讨论; 2014年有一个人说k-sum问题, lower bound就是N^ceiling(k/2), 不过2016年的时候有人发帖, Wiki上面有人提出了优于N^2的解法;
这个是另外一个很奇葩的解法:
// No hashmaps and no sorting, but may require
// a lot of memory if the range of numbers in nums[] is pretty big.
// Basic idea - use integers from nums[] as indices
// in a new array - call it histogram. Then number at
// index x in this histogram would represent number of
// elements in nums[] equal to x
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Integer[] hist;
List<List<Integer>> ret;
ret = new ArrayList<List<Integer>>();
if (nums.length < 3)
return ret;
// Loop 1 - determine bounds [sMin,sMax]
// Any number from nums[] outside of these bounds
// cannot make a tulip (a,b,c) where a+b+c=0
Integer max1 = null, max2 = null, min1 = null, min2 = null;
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
max1 = min1 = nums[0];
} else {
if (nums[i] < min1){
min2 = min1;
min1 = nums[i];
}
else if (min2 == null || nums[i] < min2)
min2 = nums[i];
if (nums[i] > max1){
max2 = max1;
max1 = nums[i];
}
else if (max2 == null || nums[i] > max2)
max2 = nums[i];
}
}
int sMin = Math.max(min1, 0 - max1 - max2);
int sMax = Math.min(max1, 0 - min1 - min2);
int offset = -sMin;
int size = sMax - sMin + 1;
if (size < 1)
return ret;
hist = new Integer[size];
// Loop 2 - build histogram - array with indices matching
// numbers from input nums[] array restricted to [sMin,sMax] range.
// This histogram has more elements than distinct set of valid input integers.
// Some elements of histogram are nulls since their indices are not present in nums[].
// Use offset to start array from 0
for (int i = 0; i < nums.length; i++) {
if (nums[i] < sMin || nums[i] > sMax)
continue;
if (null == hist[nums[i] + offset])
hist[nums[i] + offset] = 1;
else
hist[nums[i] + offset]++;
}
// Loop 3 - loop through histogram
// In the outer loop only consider negative numbers since
// at least one number in tulip (a,b,c) should be negative
// (excluding {0,0,0} case)
for (int i = 0;i - offset < 0;i++)
{
// number a from (a,b,c) isn't present in nums[]
if (null == hist[i])
continue;
// Nested loop to find 2 more numbers in the tulip that includes number i
// Consider only tulips with elements in non-descending order
for (int j = i;j < hist.length && (j <= 3 * offset - i - j);j++)
{
// Several validations:
// when tulip (a,b,c) includes 2 equal numbers a and b
if (j == i && hist[i]<2)
continue;
// when histogram doesn't have number j
if (null == hist[j])
continue;
// when third number in the tulip is missing or is out of bound
if (3*offset - i - j < 0 || 3*offset - i - j >= size || null == hist[3*offset - i - j])
continue;
// when tulip (a,b,c) includes 2 equal numbers b and c
if ((j == 3 * offset - i - j) && hist[j] < 2 )
continue;
// if we got here - add a valid tulip
ret.add(Arrays.asList(i - offset,j - offset, 2*offset - i - j));
}
}
// Handle case when array includes 3 zeros
if (null!= hist[offset] && hist[offset] >= 3)
ret.add(Arrays.asList(0,0,0));
return ret;
}
}
大概思路其实就是用hashing来实现sorting的过程, 具体做法没有看了. 用hashing这一题的问题在于将会需求大量的空间, 然后hashing出来的这个结果(比如是counts array)比普通的sorted array要难处理很多;
Problem Description
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: 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]
]
Difficulty:Medium
Total Accepted:229.7K
Total Submissions:1.1M
Contributor: LeetCode
Companies
amazon microsoft bloomberg facebook adobe works applications
Related Topics
array two pointers
Similar Questions
Two Sum 3Sum Closest 4Sum 3Sum Smaller