每日一道 LeetCode (52)：三數(shù)之和

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：三數(shù)之和

難度：「中等」

題目來源：https://leetcode-cn.com/problems/3sum/

給你一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例：

給定數(shù)組?nums?=?[-1,?0,?1,?2,?-1,?-4]，

滿足要求的三元組集合為：
[
??[-1,?0,?1],
??[-1,?-1,?2]
]

解題思路

之前一段時間都在寫 JVM 和 Tomcat 的一系列相關(guān)的文章，刷力扣題就給空下了，今天開始接著撿起來做題。

首先這道題我第一個反應(yīng)是套三個循環(huán)，肯定做得出來，時間復(fù)雜度是 O(n^3) ，放在力扣里面，按照一貫的尿性結(jié)果肯定是超時，這個方案我現(xiàn)在都已經(jīng)懶得寫了（對，我現(xiàn)在就是這么飄），除了鍛煉下寫代碼的能力，對于算法好像沒啥提升。

其他的方案又想不出來，沒辦法，只能去翻答案。

答案上的思路就很有意思了，第一件事兒就是先給數(shù)組排序，把這個數(shù)組變成一個有序數(shù)組。

三個數(shù)加起來結(jié)果要是 0 ，會有一種特殊情況就是 0 + 0 + 0 = 0 。

刨除掉上面這種情況，那么肯定第一位是負(fù)數(shù)，后面第二位只能比第一位大，第三位要比第二位大（這不是顯而易見嘛）。

套上前面的特殊情況，那么會有一個確定的關(guān)系 a <= b <= c 。

這個問題解到這里，還是沒有跳脫出來三重循環(huán)，那么時間復(fù)雜度依然還是 O(n^3) ，這肯定不行，還需要繼續(xù)優(yōu)化。

目標(biāo)放在把時間復(fù)雜度降低到 O(n^2) 上，那么就是兩重循環(huán)要搞定所有的事兒，最外層的循環(huán)也就是找 a 的那個循環(huán)，這個肯定是無法避免的，能玩的滑頭也就只剩下第二重循環(huán)了，在找 b 和 c 的過程，想辦法找到內(nèi)在的聯(lián)系，在一次循環(huán)中，直接把 b 和 c 全都找出來。

如果我們固定了 a 和 b ，那么只會有一個唯一的 c 來滿足 a + b + c = 0 。當(dāng)?shù)诙匮h(huán)往后再循環(huán)一個 b1 的時候，這時如果存在 a + b1 + c1 = 0 ，那么這個 c1 一定要比之前的 c 來的要小。

這樣我們可以在第二重循環(huán)里面考慮一個雙指針的方案，一個數(shù)組從小到大排列，取 b 的時候我們從小到大取，取 c 的時候我們從大到小來取，這時，我們?nèi)?b 和 c 其實是并列在第二重里面的，這樣我們強行把三重循環(huán)降成了兩重循環(huán)。

這里的 b 和 c 可以抽象成兩個指針，左指針和右指針，左指針每像右移動一位，右指針向左有可能移動 n 位，這和數(shù)組的元素有關(guān)，最差情況下會達(dá)到移動 n 次，因此，時間復(fù)雜度也是 O(n) ，第一重循環(huán)還有一個 O(n) ，所以整體的時間復(fù)雜度會達(dá)到 O(n^2) 。

代碼：

public?List>?threeSum(int[]?nums)?{
????int?n?=?nums.length;
????Arrays.sort(nums);
????List>?ans?=?new?ArrayList<>();
????//?最外層循環(huán)，迭代?a
????for?(int?a?=?0;?a?????????//?由于元素不能重復(fù)，遇到相同的直接下次循環(huán)
????????if?(a?>?0?&&?nums[a]?==?nums[a?-?1])?{
????????????continue;
????????}
????????//?c?對應(yīng)的指針初始指向數(shù)組的最右端
????????int?c?=?n?-?1;
????????int?target?=?-nums[a];
????????//?迭代?b
????????for?(int?b?=?a?+?1;?b?????????????//?一樣先判斷是否和上次迭代的元素是否相同
????????????if?(b?>?a?+?1?&&?nums[b]?==?nums[b?-?1])?{
????????????????continue;
????????????}
????????????//?b?的位置在?c?的左側(cè)
????????????while?(b??target)?{
????????????????--c;
????????????}
????????????//?如果出現(xiàn)了指針重合，就可以退出循環(huán)了，說明沒找到對應(yīng)的?c
????????????if?(b?==?c)?{
????????????????break;
????????????}
????????????//?如果出現(xiàn)了?b?和?c?加起來等于?-a?，說明我們找到的最后的結(jié)果
????????????if?(nums[b]?+?nums[c]?==?target)?{
????????????????List?list?=?new?ArrayList<>();
????????????????list.add(nums[a]);
????????????????list.add(nums[b]);
????????????????list.add(nums[c]);
????????????????ans.add(list);
????????????}
????????}
????}
????return?ans;
}

?

不知道各位還記不記得之前兩數(shù)之和的解法，當(dāng)我們確定了 a 和 b 以后，最終尋找 c 的時候還可以把整個數(shù)組放在一個哈希表中，通過哈希表的特性來判斷當(dāng)前 c 是否存在，如果不存在，則進(jìn)入下一次循環(huán)。

?