共计 2405 个字符，预计需要花费 7 分钟才能阅读完成。
本篇内容主要讲解“Java 怎么求三个数是否为零”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让丸趣 TV 小编来带大家学习“Java 怎么求三个数是否为零”吧!
简单的做法，根据 2Sum，遍历 3 次，此时时间复杂度是 O(n 的 3 次方)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
* Created by lifei on 16/5/29.
*/
public class ThreeSum {
/**
*
* 暴力解决法是每个人都能想到的，三层 for 循环，时间复杂度是 O(n^3)，而且还要处理重复的问题，显然不是题目想要的解法。 那能不能降到 O(n^2)？排序算法的时间复杂度为 O(nlgn)，小于 O(n^2)，那么我们不妨先对数组排个序。 *
* 排序之后，我们就可以对数组用两个指针分别从前后两端向中间扫描了，如果是 2Sum，我们找到两个指针之和为 target 就 OK 了， * 那 3Sum 类似，我们可以先固定一个数，然后找另外两个数之和为第一个数的相反数就可以了。 *
* 做过 leetcode 的人都知道, 里面有 2sum, 3sum(closest), 4sum 等问题, 这些也是面试里面经典的问题, 考察是否能够合理利用排序这个性质,
* 一步一步得到高效的算法. 经过总结, 本人觉得这些问题都可以使用一个通用的 K sum 求和问题加以概括消化,
* 这里我们先直接给出 K Sum 的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的 K,
* 比如 leetcode 中的 2Sum, 3Sum, 4Sum 问题. 同时我们也给出另一种哈希算法的讨论.
*
*
K Sum 求解方法, 适用 leetcode 2Sum, 3Sum, 4Sum： 方法一： 暴力，就是枚举所有的 K -subset, 那么这样的复杂度就是 从 N 选出 K 个，复杂度是 O(N^K)
方法二： 排序
2sum 的算法复杂度是 O(NlogN) 因为排序用了 N log N 以及头尾指针的搜索是线性的，所以总体是 O(NlogN)， 好了现在考虑 3sum, 有了 2sum 其实 3sum 就不难了，这样想： 先取出一个数，那么我只要在剩下的数字里面找到两个数字使得他们的和等于 (target – 那个取出的数) 就可以了吧。所以 3sum 就退化成了 2sum,
取出一个数字，这样的数字有 N 个，所以 3sum 的算法复杂度就是 O(N^2 ), 注意这里复杂度是 N 平方，因为你排序只需要排一次，后面的工作都是取出一个数字， 然后找剩下的两个数字，找两个数字是 2sum 用头尾指针线性扫，这里很容易错误的将复杂度算成 O(N^2logN)，这个是不对的。 我们继续的话 4sum 也就可以退化成 3sum 问题(copyright @sigmainfy)，那么以此类推，K-sum 一步一步退化，最后也就是解决一个 2sum 的问题， K sum 的复杂度是 O(n^(K-1))。 这个界好像是最好的界了，也就是 K -sum 问题最好也就能做到 O(n^(K-1))复杂度
K Sum (2Sum, 3Sum, 4Sum) 算法优化(Optimization)： 这里讲两点，第一，注意比如 3sum 的时候，先整体排一次序，然后枚举第三个数字的时候不需要重复， 比如排好序以后的数字是 a b c d e f, 那么第一次枚举 a, 在剩下的 b c d e f 中进行 2 sum, 完了以后第二次枚举 b,
只需要在 c d e f 中进行 2sum 好了，而不是在 a c d e f 中进行 2sum, 这个大家可以自己体会一下，想通了还是挺有帮助的。 第二，K Sum 可以写一个递归程序很优雅的解决，具体大家可以自己试一试。写递归的时候注意不要重复排序就行了。 */
List List Integer ret = new ArrayList List Integer ();
public List List Integer threeSum(int[] num) { if (num == null || num.length 3) return ret;
Arrays.sort(num);
int len = num.length;
for (int i = 0; i len-2; i++) { if (i 0 num[i] == num[i-1]) continue;
find(num, i+1, len-1, num[i]); // 寻找两个数与 num[i]的和为 0
}
return ret;
}
public void find(int[] num, int begin, int end, int target) {
int l = begin, r = end;
while (l r) { if (num[l] + num[r] + target == 0) {
List Integer ans = new ArrayList Integer
ans.add(target);
ans.add(num[l]);
ans.add(num[r]);
ret.add(ans); // 放入结果集中
while (l r num[l] == num[l+1]) l++;
while (l r num[r] == num[r-1]) r--;
l++;
r--;
} else if (num[l] + num[r] + target 0) {
l++;
} else {
r--;
}
}
}
}到此，相信大家对“Java 怎么求三个数是否为零”有了更深的了解，不妨来实际操作一番吧！这里是丸趣 TV 网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
正文完
