【算法专题突破】双指针 - 三数之和（7）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 三数之和（7）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

题目链接：15. 三数之和 - 力扣（Leetcode）

【算法专题突破】双指针 - 三数之和（7）,算法专题训练,算法,c++,leetcode

题目就是要找出和为0的不重复的三元组，

注意三元组的每个元素是得不同的位置，那不重复又是什么意思呢？

我们可以看第一个示例，

他找出了三个三元组，但是他最后只返回了两个，

也就是，三元组的元素相同算同一个三元组。（如果没有就返回空集。）

2. 算法原理

第一个想法当然是暴力枚举，具体来说就是，

先排序，然后暴力枚举，最后用set去重就行，

那我们就得想一想怎么把N3的暴力枚举优化一下，

排序之后是有序数组，那我们就得想到改用二分还是双指针来优化：当然是优先双指针啦

来看具体解法：

固定一个 i 位置：

【算法专题突破】双指针 - 三数之和（7）,算法专题训练,算法,c++,leetcode

我们只需要通过双指针快速找到 left 位置 + right 位置的和是 4 的位置即可。

3. 代码编写

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1, right = nums.size() - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum < 0) left++;
                else if(sum > 0) right--;
                else { // sum == 0
                    ans.push_back({nums[i], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(left < right && nums[right] == nums[right - 1]) right--;
                    left++, right--;
                }
            }
            while(i < nums.size() - 2 && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
};