leetcode 算法 数据结构 力扣18：三数之和

15. 三数之和 - 力扣（LeetCode）

题意：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

三元组不可以重复，但是三元组里的元素可以重复，比如[1,1,1]就可以

但是[-1,0,1]与[-1,0,1]或[0,-1,1]就是重复的，不可以。

思路：因为不要求返回三元组的元素的下标，只需要返回符合条件的三元组的元素，所以为了后续处理方便，先用sort对整个数组排序。

然后再使用双指针法，i指针负责从左到右依次遍历整个数组的元组（for循环），也就是a。left在i+1位置，right在数组末尾。

（while循环）对i、left、right三个位置的值相加，如果小于0，那么left右移一位，如果大于0，right左移一位。如果等于0，直接返回这三个元素，然后left和right同时向中间移动一个位置。直到left和right移动到相同位置，结束循环，所以while循环的条件是left

尤其需要注意的是去重（去重的一个原则是在使用后再判断是否与前一个位置的元素重复）：

去重就要求分别对a、b、c三个元素都要去重，因为三元组是元素的组合，假设遍历到a1时，满足条件的b、c有三组，a1的下一个位置a2的值等于a1，如果不对a去重的话，就会多出来三组重复的三元组。同理，b、c也一样，所以需要对a、b、c分别去重。

对a去重：

在用i对数组遍历的for循环中，先判断nums[i]是否等于nums[i-1]，也就是看当前位置的a与前一个a是否相同，如果相同，直接continue，移动到下一个位置。

要注意，去重是要判断当前位置与前一位置（已经使用过）的元素是否相同，而不是判断当前位置与当前位置的下一个位置是否相同，因为下一位置有可能是符合条件的与当前位置相等的b元素，容易被错过。不能有重复的三元组，但三元组内的元素是可以重复的！

对b、c去重：

在获得了符合条件的三元数组后，也就是使用完b、c后，进行去重。

对b来说，while循环判断nums[left+1]是否与nums[left]相等，如果相等，则left往后移动一位，直到不相等，或者left没法往后面移动，即left不小于right。

对c来说同理，如果nums[right-1]与nums[right]相等，则right往前移动一位，直到不相等。或left不小于right。

对b、c去重完后，此时left和right已经移动到了最后一个不重复的有效元素位置，下一个元素与该位置的元素是不相同的。而且已经把这组元素放到result里面了，下一步要对left++,right--，找下一组符合条件的元素。

class Solution {

public:

vector> threeSum(vector& nums) {

vector> result;

sort(nums.begin(), nums.end());

// 找出a + b + c = 0

// a = nums[i], b = nums[left], c = nums[right]

for (int i = 0; i < nums.size(); i++) {

// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了

if (nums[i] > 0) {

return result;

}

// 错误去重a方法，将会漏掉-1,-1,2 这种情况

/*

if (nums[i] == nums[i + 1]) {

continue;

}

*/

// 正确去重a方法

if (i > 0 && nums[i] == nums[i - 1]) {

continue;

}

int left = i + 1;

int right = nums.size() - 1;

while (right > left) {

// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组

/*

while (right > left && nums[right] == nums[right - 1]) right--;

while (right > left && nums[left] == nums[left + 1]) left++;

*/

if (nums[i] + nums[left] + nums[right] > 0) right--;

else if (nums[i] + nums[left] + nums[right] < 0) left++;

else {

result.push_back(vector{nums[i], nums[left], nums[right]});

// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重

while (right > left && nums[right] == nums[right - 1]) right--;

while (right > left && nums[left] == nums[left + 1]) left++;

// 找到答案时，双指针同时收缩

right--;

left++;

}

}

}

return result;

}

};

总结：本题目主要用的是排序+双指针的思路，指针如何移动，还有比较重要的细节是对a、b、c的去重。要遵循先使用后去重的原则，先对a去重，bc的去重要在得到符合条件的元素后，进行去重。

参考：代码随想录

文章链接

 您阅读本篇文章共花了：