給你一個整數數組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請你返回所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。

示例 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 。

提示：
3 <= nums.length <= 3000
$?10^5$ <= nums[i] <= $10^5$

---

知識點：
數組、雙指針、排序、問題轉換為兩數之和

---

解：
首先，我沒考慮到最暴力的三個嵌套for循環，因為它的復雜度非常大，而本題的核心考點就是雙指針，因此需要考慮如何將問題轉換為求雙指針的問題。
一個很簡單的思路，就是固定其中一個數，去處理另外兩個數，因此，用for循環代表第一個數的遍歷。
因為題目要求結果不能包含重復的三元組，因此：
①將原始數組進行升序排序，再去遍歷，得到的三元組的數字滿足a≤b≤c，這樣就不會出現b,a,c等順序，因此能避免結果出現重復的三元組。
②在每次遍歷中，當前處理的數字，不能和上一次遍歷處理的數字相同，例如：當前第二個元素、上一次遍歷的第二個元素相同，那么這樣就會產生重復。因此，當遇到和上一次遍歷相同的數字，就跳過當前這個數字的遍歷。

基于這個分析，在對pi的for循環遍歷中，定義雙指針pj、pk，分別用于遍歷第二個數、第三個數，并根據#兩數之和這道題的思路，兩個指針從兩端開始向中間遍歷，只要左指針指向的數字＜右指針指向的數字，就繼續循環。
對于每次得到的第二個數、第三個數，我們計算三數之和sum，并有以下三種情況：
①若和為0，滿足條件，就構造List，存到結果列表中。然后要更新雙指針。但首先，需要判斷指針遍歷的元素是否與上一次遍歷的元素相同，若相同，則讓指針向右/左移動一格。接下來，再去同時更新雙指針（這里需要同時更新雙指針，是因為：小的那個數變大，為了保持和不變，大的那個數要同時變小）。
②若和＜0，表示我們要獲得更大的一個數，由于第三個數代表的是三元組中最大的數，因此我們讓代表第二個數的左指針右移一格。
③若和＞0，表示我們要獲得更小的一個數，由于第二個數代表的是三元組中最小的數（此時我們固定了第一個數，因此可以這么描述），因此我們讓代表第三個數的右指針左移一格。

時間復雜度：$O(n^2)$
空間復雜度：$O(n)$，由于對原始數組進行了排序，因此可視為使用一個額外的數組存儲了nums的副本并進行排序 【該分析源自力扣官解】

class Solution {public List<List<Integer>> threeSum(int[] nums) {//目標：數組的三個不同數字和為0//定義最終結果的數據結構List<List<Integer>> res = new ArrayList<>();//數組長度int n = nums.length;//原數組進行排序，實現最終結果的去重Arrays.sort(nums);//遍歷所有元素for (int pi = 0; pi < n - 2; pi++) {//當前遍歷的第一個元素需要不等于前一個元素，以降低時間復雜度if (pi > 0 && nums[pi] == nums[pi - 1]) {continue;}//問題轉化為：固定第一個數的情況下，對另外兩個數進行常規雙指針操作//定義雙指針int pj = pi + 1;int pk = n - 1;//只要左指針＜右指針，就繼續循環while (pj < pk) {//計算三數之和int sum = nums[pi] + nums[pj] + nums[pk];if (sum == 0) {//滿足要求，加入resList<Integer> triplets = new ArrayList<>();triplets.addAll(Arrays.asList(nums[pi], nums[pj], nums[pk]));//一次性添加三個元素res.add(triplets);//跳過重復元素while (pj < pk && nums[pj] == nums[pj + 1])pj++;while (pj < pk && nums[pk] == nums[pk - 1])pk--;//更新雙指針（小的那個數變大，為了保持和不變，大的那個數要同時變小）pj++;pk--;} else if (sum < 0) {//和小于0，尋找比第二小的數稍微大一點的數pj++;} else {//和大于0，尋找比第一大的數稍微小一點的數pk--;}}}return res;}
}