經(jīng)常刷 LeetCode 的讀者肯定知道鼎鼎有名的 twoSum 問(wèn)題择膝，我們的舊文 Two Sum 問(wèn)題的核心思想 對(duì) twoSum 的幾個(gè)變種做了解析誓琼。
但是除了 twoSum 問(wèn)題，LeetCode 上面還有 3Sum肴捉，4Sum 問(wèn)題腹侣，我估計(jì)以后出個(gè) 5Sum，6Sum 也不是不可能齿穗。
那么傲隶，對(duì)于這種問(wèn)題有沒有什么好辦法用套路解決呢？本文就由淺入深窃页，層層推進(jìn)跺株，用一個(gè)函數(shù)來(lái)解決所有 nSum 類型的問(wèn)題。
labuladong算法小抄
一脖卖、twoSum 問(wèn)題
力扣上的 twoSum 問(wèn)題乒省，題目要求返回的是索引，這里我來(lái)編一道 twoSum 題目畦木，不要返回索引袖扛，返回元素的值：
如果假設(shè)輸入一個(gè)數(shù)組 nums 和一個(gè)目標(biāo)和 target，請(qǐng)你返回 nums 中能夠湊出 target 的兩個(gè)元素的值十籍，比如輸入 nums = [5,3,1,6], target = 9蛆封，那么算法返回兩個(gè)元素 [3,6]〖宋恚可以假設(shè)只有且僅有一對(duì)兒元素可以湊出 target娶吞。
我們可以先對(duì) nums 排序，然后利用左右雙指針技巧械姻，從兩端相向而行就行了：
vector<int> twoSum(vector<int>& nums, int target) {
// 先對(duì)數(shù)組排序
sort(nums.begin(), nums.end());
// 左右指針
int lo = 0, hi = nums.size() - 1;
while (lo < hi)
{
int sum = nums[lo] + nums[hi];
// 根據(jù) sum 和 target 的比較妒蛇，移動(dòng)左右指針
if (sum < target)
lo++;
else if (sum > target)
hi--;
else if (sum == target)
return { nums[lo], nums[hi] };
}
return {};
}
這樣就可以解決這個(gè)問(wèn)題，不過(guò)我們要繼續(xù)魔改題目楷拳，把這個(gè)題目變得更泛化绣夺，更困難一點(diǎn)：
nums 中可能有多對(duì)兒元素之和都等于 target，請(qǐng)你的算法返回所有和為 target 的元素對(duì)兒欢揖，其中不能出現(xiàn)重復(fù)觅够。
比如說(shuō)輸入為 nums = [1,3,1,2,2,3], target = 4，那么算法返回的結(jié)果就是：[[1,3],[2,2]]娘汞。
對(duì)于修改后的問(wèn)題，關(guān)鍵難點(diǎn)是現(xiàn)在可能有多個(gè)和為 target 的數(shù)對(duì)兒泊碑，還不能重復(fù)，比如上述例子中 [1,3] 和 [3,1] 就算重復(fù)毯欣，只能算一次馒过。
首先，基本思路肯定還是排序加雙指針：
vector<vector<int>> towSumTarget(vector<int>& nums, int target)
{
// 先對(duì)數(shù)組排序
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int lo = 0, hi = nums.size() - 1;
while (lo < hi)
{
int sum = nums[lo] + nums[hi];
// 根據(jù) sum 和 target 的比較酗钞，移動(dòng)左右指針
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.push_back({nums[lo], nums[hi]});
lo++;
hi--;
}
}
return res;
}
但是腹忽，這樣實(shí)現(xiàn)會(huì)造成重復(fù)的結(jié)果，比如說(shuō) nums = [1,1,1,2,2,3,3], target = 4砚作，得到的結(jié)果中 [1,3] 肯定會(huì)重復(fù)窘奏。
出問(wèn)題的地方在于 sum == target 條件的 if 分支，當(dāng)給 res 加入一次結(jié)果后葫录，lo 和 hi 不應(yīng)該改變 1 的同時(shí)着裹，還應(yīng)該跳過(guò)所有重復(fù)的元素：
所以，可以對(duì)雙指針的 while 循環(huán)做出如下修改：
while (lo < hi)
{
int sum = nums[lo] + nums[hi];
// 記錄索引 lo 和 hi 最初對(duì)應(yīng)的值
int left = nums[lo], right = nums[hi];
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.push_back({ left, right });
// 跳過(guò)所有重復(fù)的元素
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
這樣就可以保證一個(gè)答案只被添加一次压昼，重復(fù)的結(jié)果都會(huì)被跳過(guò)求冷，可以得到正確的答案。不過(guò)窍霞，受這個(gè)思路的啟發(fā)匠题，其實(shí)前兩個(gè) if 分支也是可以做一點(diǎn)效率優(yōu)化，跳過(guò)相同的元素：
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
// nums 數(shù)組必須有序
sort(nums.begin(), nums.end());
int lo = 0, hi = nums.size() - 1;
vector<vector<int>> res;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
}
else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
}
else {
res.push_back({ left, right });
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
return res;
}
這樣但金，一個(gè)通用化的 twoSum 函數(shù)就寫出來(lái)了韭山，請(qǐng)確保你理解了該算法的邏輯，我們后面解決 3Sum 和 4Sum 的時(shí)候會(huì)復(fù)用這個(gè)函數(shù)冷溃。
這個(gè)函數(shù)的時(shí)間復(fù)雜度非常容易看出來(lái)钱磅，雙指針操作的部分雖然有那么多 while 循環(huán)，但是時(shí)間復(fù)雜度還是 O(N)似枕，而排序的時(shí)間復(fù)雜度是 O(NlogN)盖淡，所以這個(gè)函數(shù)的時(shí)間復(fù)雜度是 O(NlogN)。
二凿歼、3Sum 問(wèn)題
這樣褪迟，我們?cè)俜夯幌骂}目，不要光和為 0 的三元組了答憔，計(jì)算和為 target 的三元組吧味赃，同上面的 twoSum 一樣，也不允許重復(fù)的結(jié)果：
這個(gè)問(wèn)題怎么解決呢虐拓？很簡(jiǎn)單心俗，窮舉唄。現(xiàn)在我們想找和為 target 的三個(gè)數(shù)字，那么對(duì)于第一個(gè)數(shù)字城榛，可能是什么揪利？nums 中的每一個(gè)元素 nums[i] 都有可能！
那么吠谢，確定了第一個(gè)數(shù)字之后土童，剩下的兩個(gè)數(shù)字可以是什么呢？其實(shí)就是和為 target - nums[i] 的兩個(gè)數(shù)字唄工坊，那不就是 twoSum 函數(shù)解決的問(wèn)題么？??
可以直接寫代碼了敢订，需要把 twoSum 函數(shù)稍作修改即可復(fù)用：
vector<vector<int>> threeSumTarget(vector<int>& nums, int target)
{
// 數(shù)組得排個(gè)序
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
// 窮舉 threeSum 的第一個(gè)數(shù)
for (int i = 0; i < n; i++)
{
// 對(duì) target - nums[i] 計(jì)算 twoSum
vector<vector<int>> tuples = twoSumTarget(nums, i + 1, target - nums[i]);
// 如果存在滿足條件的二元組王污，再加上 nums[i] 就是結(jié)果三元組
for (vector<int>& tuple : tuples)
{
tuple.push_back(nums[i]);
res.push_back(tuple);
}
// 跳過(guò)第一個(gè)數(shù)字重復(fù)的情況，否則會(huì)出現(xiàn)重復(fù)結(jié)果
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
需要注意的是楚午，類似 twoSum昭齐，3Sum 的結(jié)果也可能重復(fù)，比如輸入是 nums = [1,1,1,2,3], target = 6矾柜，結(jié)果就會(huì)重復(fù)阱驾。
關(guān)鍵點(diǎn)在于，不能讓第一個(gè)數(shù)重復(fù)怪蔑，至于后面的兩個(gè)數(shù)里覆，我們復(fù)用的 twoSum 函數(shù)會(huì)保證它們不重復(fù)。所以代碼中必須用一個(gè) while 循環(huán)來(lái)保證 3Sum 中第一個(gè)元素不重復(fù)缆瓣。
至此喧枷，3Sum 問(wèn)題就解決了，時(shí)間復(fù)雜度不難算弓坞，排序的復(fù)雜度為 O(NlogN)隧甚，twoSumTarget 函數(shù)中的雙指針操作為 O(N)，threeSumTarget 函數(shù)在 for 循環(huán)中調(diào)用 twoSumTarget 所以總的時(shí)間復(fù)雜度就是 O(NlogN + N^2) = O(N^2)渡冻。
三戚扳、4Sum 問(wèn)題
都到這份上了，4Sum 完全就可以用相同的思路：窮舉第一個(gè)數(shù)字族吻，然后調(diào)用 3Sum 函數(shù)計(jì)算剩下三個(gè)數(shù)帽借，最后組合出和為 target 的四元組。
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 數(shù)組需要排序
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
// 窮舉 fourSum 的第一個(gè)數(shù)
for (int i = 0; i < n; i++) {
// 對(duì) target - nums[i] 計(jì)算 threeSum
vector<vector<int>>
triples = threeSumTarget(nums, i + 1, target - nums[i]);
// 如果存在滿足條件的三元組呼奢，再加上 nums[i] 就是結(jié)果四元組
for (vector<int>& triple : triples) {
triple.push_back(nums[i]);
res.push_back(triple);
}
// fourSum 的第一個(gè)數(shù)不能重復(fù)
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
/* 從 nums[start] 開始宜雀，計(jì)算有序數(shù)組
* nums 中所有和為 target 的三元組 */
vector<vector<int>>
threeSumTarget(vector<int>& nums, int start, int target) {
int n = nums.size();
vector<vector<int>> res;
// i 從 start 開始窮舉，其他都不變
for (int i = start; i < n; i++) {
...
}
return res;
}
這樣握础，按照相同的套路辐董，4Sum 問(wèn)題就解決了，時(shí)間復(fù)雜度的分析和之前類似禀综，for 循環(huán)中調(diào)用了 threeSumTarget 函數(shù)简烘，所以總的時(shí)間復(fù)雜度就是 O(N^3)苔严。
四、100Sum 問(wèn)題孤澎？
在 LeetCode 上届氢，4Sum 就到頭了，但是回想剛才寫 3Sum 和 4Sum 的過(guò)程覆旭，實(shí)際上是遵循相同的模式的退子。我相信你只要稍微修改一下 4Sum 的函數(shù)就可以復(fù)用并解決 5Sum 問(wèn)題，然后解決 6Sum 問(wèn)題……
那么型将，如果我讓你求 100Sum 問(wèn)題寂祥，怎么辦呢？其實(shí)我們可以觀察上面這些解法七兜，統(tǒng)一出一個(gè) nSum 函數(shù)：
/* 注意：調(diào)用這個(gè)函數(shù)之前一定要先給 nums 排序 */
vector<vector<int>> nSumTarget(
vector<int>& nums, int n, int start, int target) {
int sz = nums.size();
vector<vector<int>> res;
// 至少是 2Sum丸凭，且數(shù)組大小不應(yīng)該小于 n
if (n < 2 || sz < n) return res;
// 2Sum 是 base case
if (n == 2) {
// 雙指針那一套操作
int lo = start, hi = sz - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.push_back({left, right});
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
} else {
// n > 2 時(shí)，遞歸計(jì)算 (n-1)Sum 的結(jié)果
for (int i = start; i < sz; i++) {
vector<vector<int>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (vector<int>& arr : sub) {
// (n-1)Sum 加上 nums[i] 就是 nSum
arr.push_back(nums[i]);
res.push_back(arr);
}
while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
}
}
return res;
}
嗯腕铸，看起來(lái)很長(zhǎng)惜犀，實(shí)際上就是把之前的題目解法合并起來(lái)了，n == 2 時(shí)是 twoSum 的雙指針解法狠裹，n > 2 時(shí)就是窮舉第一個(gè)數(shù)字虽界，然后遞歸調(diào)用計(jì)算 (n-1)Sum，組裝答案酪耳。
需要注意的是浓恳，調(diào)用這個(gè) nSum 函數(shù)之前一定要先給 nums 數(shù)組排序，因?yàn)?nSum 是一個(gè)遞歸函數(shù)碗暗，如果在 nSum 函數(shù)里調(diào)用排序函數(shù)颈将，那么每次遞歸都會(huì)進(jìn)行沒有必要的排序，效率會(huì)非常低言疗。
比如說(shuō)現(xiàn)在我們寫 LeetCode 上的 4Sum 問(wèn)題：
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
// n 為 4晴圾，從 nums[0] 開始計(jì)算和為 target 的四元組
return nSumTarget(nums, 4, 0, target);
}
再比如 LeetCode 的 3Sum 問(wèn)題，找 target == 0 的三元組：
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
// n 為 3噪奄，從 nums[0] 開始計(jì)算和為 0 的三元組
return nSumTarget(nums, 3, 0, 0);
}
那么死姚，如果讓你計(jì)算 100Sum 問(wèn)題，直接調(diào)用這個(gè)函數(shù)就完事兒了勤篮。
