Java怎么求三個(gè)數(shù)是否為零

本篇內(nèi)容主要講解“Java怎么求三個(gè)數(shù)是否為零”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java怎么求三個(gè)數(shù)是否為零”吧!

簡(jiǎn)單的做法，根據(jù)2Sum，遍歷3次，此時(shí)時(shí)間復(fù)雜度是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 {

    /**
     *
     * 暴力解決法是每個(gè)人都能想到的，三層for循環(huán)，時(shí)間復(fù)雜度是O(n^3)，而且還要處理重復(fù)的問(wèn)題，顯然不是題目想要的解法。

       那能不能降到O(n^2)？排序算法的時(shí)間復(fù)雜度為O(nlgn)，小于O(n^2)，那么我們不妨先對(duì)數(shù)組排個(gè)序。
     *
     * 排序之后，我們就可以對(duì)數(shù)組用兩個(gè)指針?lè)謩e從前后兩端向中間掃描了，如果是 2Sum，我們找到兩個(gè)指針之和為target就OK了，
     * 那 3Sum 類似，我們可以先固定一個(gè)數(shù)，然后找另外兩個(gè)數(shù)之和為第一個(gè)數(shù)的相反數(shù)就可以了。
     *

     * 做過(guò)leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等問(wèn)題, 這些也是面試?yán)锩娼?jīng)典的問(wèn)題, 考察是否能夠合理利用排序這個(gè)性質(zhì),
     * 一步一步得到高效的算法. 經(jīng)過(guò)總結(jié), 本人覺(jué)得這些問(wèn)題都可以使用一個(gè)通用的K sum求和問(wèn)題加以概括消化,
     * 這里我們先直接給出K Sum的問(wèn)題描述和算法(遞歸解法), 然后將這個(gè)一般性的方法套用到具體的K,
     * 比如leetcode中的2Sum, 3Sum, 4Sum問(wèn)題. 同時(shí)我們也給出另一種哈希算法的討論.
     *
     *
     K Sum求解方法, 適用leetcode 2Sum, 3Sum, 4Sum：
     方法一： 暴力，就是枚舉所有的K-subset, 那么這樣的復(fù)雜度就是 從N選出K個(gè)，復(fù)雜度是O(N^K)
     方法二： 排序
     2sum的算法復(fù)雜度是O(NlogN) 因?yàn)榕判蛴昧薔 log N以及頭尾指針的搜索是線性的，所以總體是O(NlogN)，
     好了現(xiàn)在考慮3sum, 有了2sum其實(shí)3sum就不難了，這樣想：
     先取出一個(gè)數(shù)，那么我只要在剩下的數(shù)字里面找到兩個(gè)數(shù)字使得他們的和等于(target – 那個(gè)取出的數(shù))就可以了吧。所以3sum就退化成了2sum,
     取出一個(gè)數(shù)字，這樣的數(shù)字有N個(gè)，所以3sum的算法復(fù)雜度就是O(N^2 ), 注意這里復(fù)雜度是N平方，因?yàn)槟闩判蛑恍枰乓淮?，后面的工作都是取出一個(gè)數(shù)字，
     然后找剩下的兩個(gè)數(shù)字，找兩個(gè)數(shù)字是2sum用頭尾指針線性掃，這里很容易錯(cuò)誤的將復(fù)雜度算成O(N^2logN)，這個(gè)是不對(duì)的。
     我們繼續(xù)的話4sum也就可以退化成3sum問(wèn)題(copyright @sigmainfy)，那么以此類推，K-sum一步一步退化，最后也就是解決一個(gè)2sum的問(wèn)題，
     K sum的復(fù)雜度是O(n^(K-1))。 這個(gè)界好像是最好的界了，也就是K-sum問(wèn)題最好也就能做到O(n^(K-1))復(fù)雜度

     K Sum (2Sum, 3Sum, 4Sum) 算法優(yōu)化(Optimization)：
     這里講兩點(diǎn)，第一，注意比如3sum的時(shí)候，先整體排一次序，然后枚舉第三個(gè)數(shù)字的時(shí)候不需要重復(fù)，
     比如排好序以后的數(shù)字是 a b c d e f, 那么第一次枚舉a, 在剩下的b c d e f中進(jìn)行2 sum, 完了以后第二次枚舉b,
     只需要在 c d e f中進(jìn)行2sum好了，而不是在a c d e f中進(jìn)行2sum, 這個(gè)大家可以自己體會(huì)一下，想通了還是挺有幫助的。
     第二，K Sum可以寫(xiě)一個(gè)遞歸程序很優(yōu)雅的解決，具體大家可以自己試一試。寫(xiě)遞歸的時(shí)候注意不要重復(fù)排序就行了。
     */
    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]); //尋找兩個(gè)數(shù)與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); //放入結(jié)果集中
                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--;
            }
        }
    }

}

到此，相信大家對(duì)“Java怎么求三個(gè)數(shù)是否為零”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！