你真的會(huì)做 2 Sum 嗎？

2 Sum 這題是 Leetcode 的第一題，相信大部分小伙伴都聽(tīng)過(guò)的吧。

作為一道標(biāo)著 Easy 難度的題，它真的這么簡(jiǎn)單嗎？

我在之前的刷題視頻里說(shuō)過(guò)，大家刷題一定要吃透一類(lèi)題，為什么有的人題目做著越來(lái)越少，有的人總覺(jué)得刷不完的題，就是因?yàn)闆](méi)有分類(lèi)吃透。

單純的追求做題數(shù)量是沒(méi)有意義的，Leetcode 的題目只會(huì)越來(lái)越多，就像高三時(shí)的模考試卷一樣做不完，但分類(lèi)總結(jié)，學(xué)會(huì)解決問(wèn)題的方式方法，才能遇到新題也不手足無(wú)措。

2 Sum

這道題題意就是，給一個(gè)數(shù)組和一個(gè)目標(biāo)值，讓你在這個(gè)數(shù)組里找到兩個(gè)數(shù)，使得它倆之和等于這個(gè)目標(biāo)值的。

比如題目中給的例子，目標(biāo)值是 9，然后數(shù)組里 2 + 7 = 9，于是返回 2 和 7 的下標(biāo)。

方法一

在我多年前還不知道時(shí)空復(fù)雜度的時(shí)候，我想這還不簡(jiǎn)單嘛，就每個(gè)組合挨個(gè)試一遍唄，也就是兩層循環(huán)。

后來(lái)我才知道，這樣時(shí)間復(fù)雜度是很高的，是 O(n^2)；但另一方面，這種方法的空間復(fù)雜度最低，是 O(1)。

所以，面試時(shí)一定要先問(wèn)面試官，是希望優(yōu)化時(shí)間還是優(yōu)化空間。

一般來(lái)說(shuō)我們追求優(yōu)化時(shí)間，但你不能默認(rèn)面試官也是這么想的，有時(shí)候他就是想考你有沒(méi)有這個(gè)意識(shí)呢。

如果一個(gè)方法能夠兼具優(yōu)化時(shí)間和空間那就更好了，比如斐波那契數(shù)列這個(gè)問(wèn)題中從遞歸到 DP 的優(yōu)化，就是時(shí)間和空間的雙重優(yōu)化，不清楚的同學(xué)后臺(tái)回復(fù)「遞歸」快去補(bǔ)課～

我們來(lái)看下這個(gè)代碼：

class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{
????????for?(int?i?=?0;?i?????????????for?(int?j?=?i?+?1;?j?????????????????if?(nums[i]?+?nums[j]?==?target)?{
????????????????????return?new?int[]{i,?j};
????????????????}
????????????}
????????}
????????return?new?int[]{-1,?-1};
????}
}

• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)

喏，這速度不太行誒。

方法二

那在我學(xué)了 HashMap 這個(gè)數(shù)據(jù)結(jié)構(gòu)之后呢，我又有了新的想法。

HashMap 或者 HashSet 的最大優(yōu)勢(shì)就是能夠用 O(1) 的時(shí)間獲取到目標(biāo)值，那么是不是可以?xún)?yōu)化方法一的第二個(gè)循環(huán)呢？

有了這個(gè)思路，假設(shè)當(dāng)前在看 x，那就是需要把 x 之前或者之后的數(shù)放在 HashSet 里，然后看下 target - x 在不在這個(gè) hashSet 里，如果在的話，那就匹配成功～

誒這里有個(gè)問(wèn)題，這題要求返回這倆數(shù)的下標(biāo)，可是 HashSet 里的數(shù)是無(wú)序的...

那就用升級(jí)版——HashMap 嘛～～還不了解 HashMap 的原理的同學(xué)快去公眾號(hào)后臺(tái)回復(fù)「HashMap」看文章啦。

HashMap 里記錄下數(shù)值和它的 index 這樣匹配成功之后就可以順便得到 index 了。

這里我們不需要提前記錄所有的值，只需要邊過(guò)數(shù)組邊記錄就好了，為了防止重復(fù)，我們只在這個(gè)當(dāng)前的數(shù)出現(xiàn)之前的數(shù)組部分里找另一個(gè)數(shù)。

總結(jié)一下，

• HashMap 里記錄的是下標(biāo) i 之前的所有出現(xiàn)過(guò)的數(shù)；
• 對(duì)于每個(gè) nums[i] ，我們先檢查 target - nums[i] 是否在這個(gè) map 里；
• 如果在就直接返回了，如果不在就把當(dāng)前 i 的信息加進(jìn) map 里。

class?Solution?{
????public?int[]?twoSum(int[]?nums,?int?target)?{
????????int[]?res?=?new?int[2];
????????Map?map?=?new?HashMap<>();
????????for?(int?i?=?0;?i?????????????if?(map.containsKey(target?-?nums[i]))?{
????????????????res[0]?=?map.get(target?-?nums[i]);
????????????????res[1]?=?i;
????????????????return?res;
????????????}
????????????map.put(nums[i],?i);
????????}
????????return?res;
????}
}

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

喏，速度提升至 beat 99.96%

拓展

這是最基本的 2 Sum 問(wèn)題，這個(gè)題可以有太多的變種了：

• 如果這個(gè)數(shù)組里有不止一組結(jié)果，要求返回所有組合，該怎么做？

• 如果這個(gè)數(shù)組里有重復(fù)元素，又該怎么做？

• 如果這個(gè)數(shù)組是一個(gè)排好序了的數(shù)組，那如何利用這個(gè)條件呢？- Leetcode 167

• 如果不是數(shù)組而是給一個(gè) BST ，該怎么在一棵樹(shù)上找這倆數(shù)呢？- Leetcode 653

...

這里講一下排序數(shù)組這道題，之后會(huì)在 BST 的文章里會(huì)講 653 這題。

排序數(shù)組

我們知道排序算法中最快的也需要 O(nlogn)，所以如果是一個(gè) 2 Sum 問(wèn)題，那沒(méi)必要專(zhuān)門(mén)排序，因?yàn)榕判驎?huì)成為運(yùn)算的瓶頸。

但如果題目給的就是個(gè)排好序了的數(shù)組，那肯定要好好收著了呀！

因?yàn)楫?dāng)數(shù)組是排好序的時(shí)候，我們可以進(jìn)一步優(yōu)化空間，達(dá)到 O(n) 的時(shí)間和 O(1) 的空間。

該怎么利用排好序這個(gè)性質(zhì)呢？

那就是說(shuō)，在 x 右邊的數(shù)，都比 x 要大；在 x 左邊的數(shù)，都比 x 要小。

• 如果 x + y > target，那么就要 y 往左走，往小的方向走；

• 如果 x + y < target，那么就要 x 往右走，往大的方向走。

這也就是典型的 Two pointer 算法，兩個(gè)指針相向而行的情況，我之后也會(huì)出文章詳細(xì)來(lái)講噠。

class?Solution?{
????public?int[]?twoSum(int[]?numbers,?int?target)?{
????????int?left?=?0;
????????int?right?=?numbers.length?-?1;
????????while?(left?????????????int?sum?=?numbers[left]?+?numbers[right];
????????????if?(sum?==?target)?{
????????????????return?new?int[]{left?+?1,?right?+?1};?//Your?returned?answers?are?not?zero-based.
????????????}?else?if?(sum?????????????????left?++;
????????????}?else?{
????????????????right?--;
????????????}
????????}
????????return?new?int[]{-1,?-1};
????}
}

3 Sum

3 Sum 的問(wèn)題其實(shí)就是一個(gè) 2 Sum 的升級(jí)版，因?yàn)?1 + 2 = 3 嘛。。

那就是外面一層循環(huán)，固定一個(gè)值，在剩下的數(shù)組里做 2 Sum 問(wèn)題。

反正 3 Sum 怎么著都得 O(n^2) ，就可以先排序，反正不在乎排序的這點(diǎn)時(shí)間了，這樣就可以用 Two pointer 來(lái)做了。

還需要注意的是，這道題返回的是數(shù)值，而非 index，所以它不需要重復(fù)的數(shù)值——The solution set must not contain duplicate triplets.

class?Solution?{
????public?List>?threeSum(int[]?nums)?{
????????List>?res?=?new?ArrayList<>();
????????Arrays.sort(nums);
????????for?(int?i?=?0;?i?+?2?????????????if?(i?>?0?&&?nums[i]?==?nums[i?-?1])?{
?????????????????//?skip?same?result
????????????????continue;
????????????}
????????????int?j?=?i?+?1;
????????????int?k?=?nums.length?-?1;??
????????????int?target?=?-nums[i];
????????????while?(j?????????????????if?(nums[j]?+?nums[k]?==?target)?{
????????????????????res.add(Arrays.asList(nums[i],?nums[j],?nums[k]));
????????????????????j++;
????????????????????k--;
????????????????????while?(j?1])?{
????????????????????????j++;??//?skip?same?result
????????????????????}
????????????????????while?(j?1])?{
????????????????????????k--;??//?skip?same?result
????????????????????}
????????????????}?else?if?(nums[j]?+?nums[k]?>?target)?{
????????????????????k--;
????????????????}?else?{
????????????????????j++;
????????????????}
????????????}
????????}
????????return?res;
????}
}

4 Sum

最后就是 4 Sum 問(wèn)題啦。

這一題如果只是 O(n^3) 的解法沒(méi)什么難的，因?yàn)榫褪窃?3 Sum 的基礎(chǔ)上再加一層循環(huán)嘛。

但是如果在面試中只做出 O(n^3) 恐怕就過(guò)不了了哦?

這 4 個(gè)數(shù)，可以想成兩兩的 2 Sum，先把第一個(gè) 2 Sum 的結(jié)果存下來(lái)，然后在后續(xù)的數(shù)組中做第二個(gè) 2 Sum，這樣就可以把時(shí)間降低到 O(n^2) 了。

這里要注意的是，為了避免重復(fù)，也就是下圖的 nums[x] + nums[y] + nums[z] + nums[k] ，其實(shí)和 nums[z] + nums[k] + nums[x] + nums[y] 并沒(méi)有區(qū)別，所以我們要限制第二組的兩個(gè)數(shù)要在第一組的兩個(gè)數(shù)之后哦。

看下代碼吧：

class?Solution?{
????public?List>?fourSum(int[]?nums,?int?target)?{
????????????Set>?set?=?new?HashSet<>();
????Map>>?map?=?new?HashMap<>();
????Arrays.sort(nums);
????//?先處理第一對(duì)，把它們的sum存下來(lái)
????for(int?i?=?0;?i?3;?i++)?{
??????for(int?j?=?i?+?1;?j?2;?j++)?{
????????int?currSum?=?nums[i]?+?nums[j];
????????List>?pairs?=?map.getOrDefault(currSum,?new?ArrayList<>());
????????pairs.add(Arrays.asList(i,?j));
????????map.put(currSum,?pairs);
??????}
????}
????
????//?在其后做two?sum
????for(int?i?=?2;?i?1;?i++)?{
??????for(int?j?=?i?+?1;?j?????????int?currSum?=?nums[i]?+?nums[j];
????????List>?prevPairs?=?map.get(target?-?currSum);
????????if(prevPairs?==?null)?{
????????????continue;
????????}
????????for(List?pair?:?prevPairs)?{
??????????if(pair.get(1)?????????????set.add(Arrays.asList(nums[pair.get(0)],?nums[pair.get(1)],?nums[i],?nums[j]));
??????????}
????????}
???????}
?????}
?????return?new?ArrayList<>(set);
????}
}

好啦，以上就是 2 Sum 相關(guān)的所有問(wèn)題啦，如果有收獲的話，記得給我點(diǎn)個(gè)贊哦～

后臺(tái)回復(fù)?學(xué)習(xí)資料?領(lǐng)取學(xué)習(xí)視頻

如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝