題目來(lái)源于 LeetCode 上第 15 號(hào)問題：三數(shù)之和。

題目描述

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

題目解析

題目需要我們找出三個(gè)數(shù)且和為 0 ，那么除了三個(gè)數(shù)全是 0 的情況之外，肯定會(huì)有負(fù)數(shù)和正數(shù)，所以一開始可以先選擇一個(gè)數(shù)，然后再去找另外兩個(gè)數(shù)，這樣只要找到兩個(gè)數(shù)且和為第一個(gè)選擇的數(shù)的相反數(shù)就行了。也就是說需要枚舉 a 和 b ，將 c 的存入 map 即可。

需要注意的是返回的結(jié)果中，不能有有重復(fù)的結(jié)果。這樣的代碼時(shí)間復(fù)雜度是 O(n^2)。在這里可以先將原數(shù)組進(jìn)行排序，然后再遍歷排序后的數(shù)組，這樣就可以使用雙指針以線性時(shí)間復(fù)雜度來(lái)遍歷所有滿足題意的兩個(gè)數(shù)組合。

動(dòng)畫描述

待補(bǔ)充

代碼實(shí)現(xiàn)

class?Solution?{
public:
????vector<vector<int>>?threeSum(vector<int>&?nums)?{
????????vector<vector<int>>?res;
????????sort(nums.begin(),?nums.end());
????????if?(nums.empty()?||?nums.back()?<?0?||?nums.front()?>?0)?return?{};
????????for?(int?k?=?0;?k?<?nums.size();?++k)?{
????????????if?(nums[k]?>?0)?break;
????????????if?(k?>?0?&&?nums[k]?==?nums[k?-?1])?continue;
????????????int?target?=?0?-?nums[k];
????????????int?i?=?k?+?1,?j?=?nums.size()?-?1;
????????????while?(i?<?j)?{
????????????????if?(nums[i]?+?nums[j]?==?target)?{
????????????????????res.push_back({nums[k],?nums[i],?nums[j]});
????????????????????while?(i?<?j?&&?nums[i]?==?nums[i?+?1])?++i;
????????????????????while?(i?<?j?&&?nums[j]?==?nums[j?-?1])?--j;
????????????????????++i;?--j;
????????????????}?else?if?(nums[i]?+?nums[j]?<?target)?++i;
????????????????else?--j;
????????????}
????????}
????????return?res;
????}
};