共計(jì) 2405 個(gè)字符，預(yù)計(jì)需要花費(fèi) 7 分鐘才能閱讀完成。

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

簡單的做法，根據(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ù)的問題，顯然不是題目想要的解法。  那能不能降到 O(n^2)？排序算法的時(shí)間復(fù)雜度為 O(nlgn)，小于 O(n^2)，那么我們不妨先對數(shù)組排個(gè)序。 *
 *  排序之后，我們就可以對數(shù)組用兩個(gè)指針分別從前后兩端向中間掃描了，如果是  2Sum，我們找到兩個(gè)指針之和為 target 就 OK 了， *  那  3Sum  類似，我們可以先固定一個(gè)數(shù)，然后找另外兩個(gè)數(shù)之和為第一個(gè)數(shù)的相反數(shù)就可以了。 *
 *  做過 leetcode 的人都知道,  里面有 2sum, 3sum(closest), 4sum 等問題,  這些也是面試?yán)锩娼?jīng)典的問題,  考察是否能夠合理利用排序這個(gè)性質(zhì),
 *  一步一步得到高效的算法.  經(jīng)過總結(jié),  本人覺得這些問題都可以使用一個(gè)通用的 K  sum 求和問題加以概括消化,
 *  這里我們先直接給出 K  Sum 的問題描述和算法(遞歸解法),  然后將這個(gè)一般性的方法套用到具體的 K,
 *  比如 leetcode 中的 2Sum, 3Sum, 4Sum 問題.  同時(shí)我們也給出另一種哈希算法的討論.
 *
 *
 K Sum 求解方法,  適用 leetcode 2Sum, 3Sum, 4Sum：  方法一：  暴力，就是枚舉所有的 K -subset,  那么這樣的復(fù)雜度就是   從 N 選出 K 個(gè)，復(fù)雜度是 O(N^K)
  方法二：  排序
 2sum 的算法復(fù)雜度是 O(NlogN)  因?yàn)榕判蛴昧?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è)是不對的。  我們繼續(xù)的話 4sum 也就可以退化成 3sum 問題(copyright @sigmainfy)，那么以此類推，K-sum 一步一步退化，最后也就是解決一個(gè) 2sum 的問題， K sum 的復(fù)雜度是 O(n^(K-1))。  這個(gè)界好像是最好的界了，也就是 K -sum 問題最好也就能做到 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è)大家可以自己體會一下，想通了還是挺有幫助的。  第二，K Sum 可以寫一個(gè)遞歸程序很優(yōu)雅的解決，具體大家可以自己試一試。寫遞歸的時(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--;
 }
 }
 }
}

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