三數(shù)之和

題目鏈接 15. 三數(shù)之和

給你一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿(mǎn)足 i != j、i != k 且 j != k ，同時(shí)還滿(mǎn)足 nums[i] + nums[j] + nums[k] == 0 。請(qǐng)

你返回所有和為 0 且不重復(fù)的三元組。

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

示例 1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。

示例 2：

輸入：nums = [0,1,1]
輸出：[]
解釋：唯一可能的三元組和不為 0 。

示例 3：

輸入：nums = [0,0,0]
輸出：[[0,0,0]]
解釋：唯一可能的三元組和為 0 。

題目解釋

在數(shù)組中找到三個(gè)元素,然后讓他們的和為0,注意的是我們結(jié)果不要重復(fù).

算法原理

這個(gè)很簡(jiǎn)單,我們先排序.然后固定一個(gè)元素val,在這個(gè)前面尋找兩個(gè)元素,求他們的和為-val.這不就退化成我們的兩個(gè)元素之和了嗎.這里我們需要解決兩個(gè)問(wèn)題

• 為何當(dāng)val為最大值的時(shí)候,我們?cè)谇懊孢x兩個(gè)數(shù)一定是所有情況,這是對(duì)于每一個(gè)結(jié)果而言,我們的三個(gè)元素中一定存在一個(gè)值比較大(都為0的也是符合下面的), 我們將數(shù)組中的每一個(gè)元素都作為一個(gè)最大值,讓后遍歷整個(gè)數(shù)組,就可以收取所有情況
• 如何解決重復(fù)問(wèn)題,這里提供兩個(gè)方法,一個(gè)是都保存下來(lái),等到最后處理,麻煩.第二個(gè)是在收集結(jié)果的時(shí)候就處理了

細(xì)節(jié)補(bǔ)充

補(bǔ)充下細(xì)節(jié),我們?nèi)绾翁幚?

• 固定下最大值val, 收集結(jié)果之后跳過(guò)重復(fù)的val
• 對(duì)于收集的一次結(jié)果,跳過(guò)重復(fù)的num[left]和num[right]

代碼編寫(xiě)

class Solution
{
public:vector<vector<int>> threeSum(vector<int> &nums){vector<vector<int>> reuslt;sort(nums.begin(), nums.end());for (int i = nums.size() - 1; i >= 2;){int val = nums[i];int left = 0;int right = i - 1;while (left < right){int sum = nums[left] + nums[right];if (sum + val == 0){// 收集reuslt.push_back({nums[left], nums[right], val});// 跟新left++;right--;while (left < right && nums[left] == nums[left - 1])left++;while (left < right && nums[right] == nums[right + 1])right--;}else if (sum > -val){right--;}else{left++;}}while (i >= 2 && nums[i] == val){i--;}}return reuslt;}
};