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

?

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

?

前文合集

每日一道 LeetCode 前文合集

代碼倉(cāng)庫(kù)

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

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

題目：三數(shù)之和

難度：「中等」

題目來(lái)源：https://leetcode-cn.com/problems/3sum/

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

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

示例：

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

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

解題思路

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

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

其他的方案又想不出來(lái)，沒(méi)辦法，只能去翻答案。

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

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

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

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

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

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

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

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

這里的 b 和 c 可以抽象成兩個(gè)指針，左指針和右指針，左指針每像右移動(dòng)一位，右指針向左有可能移動(dòng) n 位，這和數(shù)組的元素有關(guān)，最差情況下會(huì)達(dá)到移動(dòng) n 次，因此，時(shí)間復(fù)雜度也是 O(n) ，第一重循環(huán)還有一個(gè) O(n) ，所以整體的時(shí)間復(fù)雜度會(huì)達(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?對(duì)應(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)了，說(shuō)明沒(méi)找到對(duì)應(yīng)的?c
????????????if?(b?==?c)?{
????????????????break;
????????????}
????????????//?如果出現(xiàn)了?b?和?c?加起來(lái)等于?-a?，說(shuō)明我們找到的最后的結(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í)候還可以把整個(gè)數(shù)組放在一個(gè)哈希表中，通過(guò)哈希表的特性來(lái)判斷當(dāng)前 c 是否存在，如果不存在，則進(jìn)入下一次循環(huán)。

?