20180319-今日算法

[gbin]

给定一个包含 n 个元素的数组 S，判断 S 中是否存在三个元素 a，b，c 使得 a + b + c = 0 ？找出所有满足条件的组合。

如 S = [-1, 0, 1, 2, -1, -4] 时， 结果为: [

[-1, 0, 1],

[-1, -1, 2]

]

来源 See leetcode

传送门：https://www.v2ex.com/t/439037

[widewing]

排序，然后从零向两边遍历？

[geelaw]

一个朴素的方法是先排序，然后枚举前两个元素再二分寻找第三个。

[WordTian]

直接三次循环相加判断，但没上面的方法有效率

[zqqian]

@geelaw 如果 max i 比较小的话，可以放到一个数组里，类似于桶排序。
可以降低一个 logn 的复杂度

[lhx2008]

做过，标准方法应该是 遍历 2 次，把答案加进 map，变成 2sum 问题，时间复杂度 n^2 空间 n^2，4sum 同理，时间复杂度 n^3

[lhx2008]

@lhx2008 遍历 2 次->两层遍历，两层 for

[gbin]

@geelaw

数小的时候枚举前两个数只和作为 key 放入 hashmap 中，不用二分法直接 O(1) 查找?

[akio]

先转变为 2sum 问题处理就明白了

[gbin]

@lhx2008 和我想的一样。就是不知道是否还有更优的算法?

[zqqian]

先排序
再枚举一个 n
然后二分剩下两个数的区间长度
然后二分两个数的位置
这样时间复杂度就是 nlognlogn
@gbin

[Mazexal]

预先枚举 c,d 得到 c+d 的 n^2 个数字并排好序。
双重 for 循环穷举 a,b 的值，再使用二分查找确定 c+d 是否存在。
c+d 的值得出来后同样枚举得出 c,d 的值。（或者在第一步就浪费一些空间将 c+d 对应的 c,d 存好，此时直接取出即可。)

[victor97]

补充题意：原题要求的是不重复的三元组。
做法：
1.先排序，假设 a<=b<=c。
2.枚举 a 的值，在 a 的后面找 b 和 c
3.b<=-a/2<=c，以-a/2 为界限，前面入栈，后面出栈，O(n)可以找出所有 bc 组合
总复杂度应该是 O(n^2)，空间复杂度 O(n)
优化：
1. 既然不重复，每个数字最多出现两次，多余可以去掉
2. a<=0, c>=0

[timle1029]

最快也就是 O(n^2) 了。Leetcode 上的原题。
先排序，然后对于每一个元素，从下一个和尾部开始搜索。

···java
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] > 0) {
return res;
}
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
while (j < k && nums[j] == nums[j + 1]) j++;
while (k > j && nums[k] == nums[k - 1]) k--;
j++;
k--;
} else if (sum > 0) {
k--;
} else {
j++;
}
}
}
return res;
}
```

[Williamongh]

支持楼主，希望能单开一个节点。

[hjdtl]

```javascript

arr.map((n,i)=>{
if(i<=arr.length-2){
for(var s=0;s<arr.length;s++){
if(s==i||s==i+1) continue;
if(arr[i]+arr[i+1]==-arr[s]){
console.log(arr[i],arr[i+1],arr[s]);
}
}
}
})

```

结果是排列，还要声明一个变量，记录下标，过滤重复的组合。

[yzyun08]

资瓷一个