題目：三數之和

排序 + 雙指針

本題的難點在于如何去除重復解。

算法流程：

1、特判，對于數組長度 n，如果數組為 null 或者數組長度小于 3，返回 []。
2、對數組進行排序。
3、遍歷排序后數組：
（1）若 nums[i]>0：因為已經排序好，所以后面不可能有三個數加和等于 0，直接返回結果。
（2）對于重復元素：跳過，避免出現重復解
（3）令左指針 L=i+1，右指針 R=n?1，當 L<R 時，執行循環：
當 nums[i]+nums[L]+nums[R]==0，執行循環，判斷左界和右界是否和下一位置重復，去除重復解。并同時將 L,R 移到下一位置，尋找新的解
若和大于 0，說明 nums[R] 太大，R 左移
若和小于 0，說明 nums[L] 太小，L 右移作者：吳彥祖
鏈接：https://leetcode.cn/problems/3sum/solutions/39722/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

代碼實現：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//特判，對于數組長度 n，如果數組為 null 或者數組長度小于 3，返回空數組if(nums.size()<3){return vector<vector<int>>();}int l,r;vector<vector<int>> result; //對數組進行排序。sort(nums.begin(), nums.end());for (int i = 0; i< nums.size(); i++){l=i+1;r = nums.size()-1;//若 nums[i]>0：因為已經排序好，所以后面不可能有三個數加和等于 0，直接返回結果。if (nums[i]>0){return result;}//難點：對于重復元素：跳過，避免出現重復解if (i>0 && nums[i] == nums[i-1]){continue;}while(r>l){if ((nums[i]+nums[l]+nums[r]) > 0){r--;}else if((nums[i]+nums[l]+nums[r]) < 0){l++;}else{vector<int> group;group.push_back(nums[i]);group.push_back(nums[l]);group.push_back(nums[r]);result.push_back(group);//去重第三個元素while(r>l && nums[r]==nums[r-1])r--;//去重第二個元素while(r>l && nums[l]==nums[l+1])l++;   r--;l++;}}   }return result;}
};