三数之和--力扣15

标题

思绪

标题要求三元组不能重复，如果使用哈希表来做，去重很复杂，而且需要额外的空间，我们这里使用双指针法直接针对数组操作。注意标题要求返回的是二维数组！
最重要的是，我们要对数组进行排序，排序后若数组中，第一个元素大于零，则后续不可能存在和即是零的三元组。
其次是对abc去重：
对a去重：当i大于0而且nums == nums[i - 1]时，说明a重复了，直接竣事本次循环。i即是0时，是第一次，所以不消去重。为什么i要大于0由于要保证i - 1大于即是0。为什么不是nums == nums[i -+1]？由于nums[i -+1]是left。
对b和c去重：在保证循环体条件right > left情况下，类似于a，判定b的后一个和c的前一个是否有重复的，如果有，b++或者c–。
代码

1. class Solution {
2. public:
3.     vector<vector<int>> threeSum(vector<int>& nums) {
4.         //返回二维数组 要求a+b+c=0
5.         vector<vector<int>> res;
6.         //排序
7.         sort(nums.begin(), nums.end());
8.         for (int i = 0; i < nums.size(); i++) {
9.             //如果排序后数组的第一个值大于零，直接返回
10.             if (nums[i] > 0) {
11.                 return res;
12.             }
13.             //对a去重
14.             if (i > 0 && nums[i] == nums[i - 1]) {
15.                 continue;
16.             }
17.             //双指针法，寻找b和c
18.             int left = i + 1;
19.             int right = nums.size() - 1;
20.             while (right > left) {
21.                 if (nums[i] + nums[left] + nums[right] > 0) {
22.                     right--;
23.                 } else if (nums[i] + nums[left] + nums[right] < 0) {
24.                     left++;
25.                 } else {
26.                     res.push_back(vector<int>{nums[i], nums[left], nums[right]});
27.                     //对b和c去重
28.                     while (right > left && nums[right] == nums[right - 1]) right--;
29.                     while (right > left && nums[left] == nums[left + 1]) left++;
31.                     //双指针收缩，继续循环
32.                     right--;
33.                     left++;
34.                 }
35.             }
36.         }
37.         return res;
38.     }
39. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。