Java怎么求三个数是否为零

共计 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 网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！