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

創(chuàng)新互聯(lián)網(wǎng)站建設服務商，為中小企業(yè)提供網(wǎng)站設計、成都網(wǎng)站設計服務，網(wǎng)站設計，網(wǎng)站托管運營等一站式綜合服務型公司，專業(yè)打造企業(yè)形象網(wǎng)站，讓您在眾多競爭對手中脫穎而出創(chuàng)新互聯(lián)。

簡單的做法，根據(jù)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循環(huán)，時間復雜度是O(n^3)，而且還要處理重復的問題，顯然不是題目想要的解法。

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

     * 做過leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等問題, 這些也是面試里面經(jīng)典的問題, 考察是否能夠合理利用排序這個性質,
     * 一步一步得到高效的算法. 經(jīng)過總結, 本人覺得這些問題都可以使用一個通用的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)，
     好了現(xiàn)在考慮3sum, 有了2sum其實3sum就不難了，這樣想：
     先取出一個數(shù)，那么我只要在剩下的數(shù)字里面找到兩個數(shù)字使得他們的和等于(target – 那個取出的數(shù))就可以了吧。所以3sum就退化成了2sum,
     取出一個數(shù)字，這樣的數(shù)字有N個，所以3sum的算法復雜度就是O(N^2 ), 注意這里復雜度是N平方，因為你排序只需要排一次，后面的工作都是取出一個數(shù)字，
     然后找剩下的兩個數(shù)字，找兩個數(shù)字是2sum用頭尾指針線性掃，這里很容易錯誤的將復雜度算成O(N^2logN)，這個是不對的。
     我們繼續(xù)的話4sum也就可以退化成3sum問題(copyright @sigmainfy)，那么以此類推，K-sum一步一步退化，最后也就是解決一個2sum的問題，
     K sum的復雜度是O(n^(K-1))。 這個界好像是最好的界了，也就是K-sum問題最好也就能做到O(n^(K-1))復雜度

     K Sum (2Sum, 3Sum, 4Sum) 算法優(yōu)化(Optimization)：
     這里講兩點，第一，注意比如3sum的時候，先整體排一次序，然后枚舉第三個數(shù)字的時候不需要重復，
     比如排好序以后的數(shù)字是 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可以寫一個遞歸程序很優(yōu)雅的解決，具體大家可以自己試一試。寫遞歸的時候注意不要重復排序就行了。
     */
    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]); //尋找兩個數(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); //放入結果集中
                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怎么求三個數(shù)是否為零”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！

分享名稱：Java怎么求三個數(shù)是否為零
瀏覽路徑：http://chinadenli.net/article14/pijhde.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導航、企業(yè)網(wǎng)站制作、小程序開發(fā)、營銷型網(wǎng)站建設、自適應網(wǎng)站、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)