Java怎么求三個數是否為零

本篇內容主要講解“Java怎么求三個數是否為零”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“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怎么求三個數是否為零”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！