【C++ leetcode】双指针（专题完结）

15. 三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

题目链接

. - 力扣（LeetCode）

画图 和 文字 分析

这道题和 两数之和等于一个值 大体思路是一样的，都是 排序 + 双指针思想

排完序后，我们定义三个指针，一个指向最后一个元素的位置，一个指向首元素的位置，另一个首元素的后一个位置

举例：

输入： [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

先固定 k不动

1. 如果三者指向的值相加为 0 ,则记录数据 ，再 j++ , k--
2. 如果三者指向的值
3. 如果三者指向的值 > 0 ，则 k--

当 i >= j （结束里层循环）

再 i++ , j = i + 1 , k = n - 1

直到 i + 1 >= k (外层循环)

做到以上，只能说完成了完成了不漏掉每一种情况，但现在还有去重的关键一步

去重需要我们在前面的基础上做更改：

第一种情况：

走完上面的步骤 :

判断现在 j 所指的内容 和 j - 1 所指内容是否相同，直到不相同为止（这里需要一个循环，此时要么，j 指向一个不和之前相重复的数，要么越界）

判断 k 同理

上面是里层循环的去重，外层循环也可以去重

当结束里层循环，完成后面的步骤 ：

判断 i 所指向的内容 和 i - 1所指向的内容是否相同，直到不相同为止

注意:

去重的时候，因为循环的缘故，一定要防止越界

 

代码

class Solution {
public:
    vector threeSum(vector& nums) 
    {
        vector t;
        sort(nums.begin(),nums.end());
        int i = 0;
        while(i + 2  0)
                {
                    k--;
                }
                else if(nums[i] + nums[j] + nums[k] = 0 && c >= 0 && d >= 0))
         {
            return false;
         }
         else if(target > 0 && (a  0) || (a > 0 && b > 0 && c > 0 && d > 0)))
         {
            return false;
         }
         else
         {
            return true;
         }
    }
    vector fourSum(vector& nums, int target) 
    {
        vector s;
        int n = nums.size() - 1;
        sort(nums.begin(),nums.end());
        int a = 0;
        while(a + 2  target - nums[c] - nums[d] )
                    {
                        d--;
                    }
                    else if(nums[a] + nums[b]