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

目录

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

---

1. 题目解析

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

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

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

我们可以看第一个示例，

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

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

2. 算法原理

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

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

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

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

来看具体解法：

固定一个 i 位置：

我们只需要通过双指针快速找到 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;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~