15. 三数之和
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 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-105 <= nums[i] <= 105
class Solution { // 哈希法，非常不推荐，又难又慢
public:// 在一个数组中找到3个数形成的三元组，它们的和为0，不能重复使用（三数下标互不相同），且三元组不能重复。// b（存储）== 0-(a+c)（检索）vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {// 如果a是正数，a<b<c，不可能形成和为0的三元组if (nums[i] > 0)break;// [a, a, ...] 如果本轮a和上轮a相同，那么找到的b，c也是相同的，所以去重aif (i > 0 && nums[i] == nums[i - 1])continue;// 这个set的作用是存储bunordered_set<int> set;for (int k = i + 1; k < nums.size(); k++) {// 去重b=c时的b和cif (k > i + 2 && nums[k] == nums[k - 1] && nums[k - 1] == nums[k - 2])continue;// a+b+c=0 <=> b=0-(a+c)int target = 0 - (nums[i] + nums[k]);if (set.find(target) != set.end()) {result.push_back({nums[i], target, nums[k]}); // nums[k]成为cset.erase(target);}else {set.insert(nums[k]); // nums[k]成为b}}}return result;}
};
class Solution { //双指针法
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> 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<int>{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;}
};
-
把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在,面试时最好不要这样用，但是如果是考试期间想不到其他方法是可以这样做的
-
其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
-
建议用双指针（这题不要求返回索引，所以可以排序，排序之后才可以用双指针）
-
双指针法的核心思路
首先对数组进行排序，用i表示当前遍历元素，left指向i+1的位置，right指向数组末尾（nums.size() - 1）
可以轻松看出，若当前的三数之和大于0，则说明和的数值大了，想让他变小，right--（已经排序过了），若小于0，则数值小了，想让他变大，left++（注意i是固定的，每次固定一个），找到等于0的时候就加到结果集里面，同时双指针收缩
但是这道题要求三元组不能是重复的，比如-1，-1，2 和 -1，-1，2 （内部元素可以重复）
去重逻辑，首先对i进行去重，num[i] == nums[i-1] 时，直接continue跳过本次遍历（进入下一个i），注意这里不能用nums[i] == nums[i+1]，因为如果这样的话，就将-1，-1，2这种结果跳过了，nums[i+1]本来应该是left最初指向的位置，这样就代表内部元素也不可以相等，不符合题意；用num[i] == nums[i-1] 这种去重逻辑，就代表前面使用过-1这个元素作为固定的i，left和right已经遍历过数组并且把-1作为固定元素的所有结果加入到结果集合里面了（应该是只多不少，因为前面的-1可以用后面的-1，但是后面的就算给他遍历也只能用他以后的数比如前面的可以用-1，-1，2也可以用-1，0，1；但是后面的只能用-1，0，1），所以直接去重跳过就好了
至于left和right的去重，因为i是固定的，left和right去重放在找到结果集之后就好（因为只有将他俩加入到结果集中则说明这一个组合已经用过了，这两个数绝对不会再用了），这样直接全部去掉之后，双指针收缩直接变成一个新的数组，如果放到加入结果集前面，这种前面0，0，0的结果集就会被漏掉