| 2024-04-18 |

# 三数之和

随笔：这题关键在于了解去重的细节

# 题目

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

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

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

示例 1：
1
2
3
4
5
6
7
8
>输入：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：
1
2
3
>输入：nums = [0,1,1]
>输出：[]
>解释：唯一可能的三元组和不为 0 。
示例 3：
1
2
3
>输入：nums = [0,0,0]
>输出：[[0,0,0]]
>解释：唯一可能的三元组和为 0 。
提示：

3 <= nums.length <= 3000

-105 <= nums[i] <= 105

思路和细节

如何移动 left 和 right 呢，如果 nums [i] + nums [left] + nums [right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。

如果 nums [i] + nums [left] + nums [right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到 left 与 right 相遇为止。

动画

15.三数之和

第一步要先对 nums 进行一遍排序

去重细节

在 i 已经固定确定的时候

判断 nums [i] == nums [i-1];

为什么判断是 i-1 而不是 i+1; 因为 i+1 可能会比如 -1 -1 2 这样的结果集给 contine 所以我从上一个进行判断上一个如果重复了

# 题解

public class Solution 
{
    public IList<IList<int>> ThreeSum(int[] nums)
        {
            IList<IList<int>> result = new List<IList<int>>(); //定义结果
            //先对nums进行排序
            Array.Sort(nums);
            //循环nums
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] > 0)
                {
                    //如果这里的结果就大于0  那就不会有三元组 a b c和为0
                    return result;
                }

                //对a进行去重  //不用i+1 防止跳过特殊情况
                if (i > 0 && nums[i] == nums[i - 1])
                {
                    continue;
                }

                //定义左右指针
                int left = i + 1;
                int right = nums.Length - 1;
                while (left < right)
                {
                    //定义结果
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum < 0) //结果小了 left右移
                    {
                        left++;
                    }
                    else if (sum > 0)
                    {
                        right--;
                    }
                    else //为0 的情况 
                    {
                        result.Add(new List<int> { nums[i], nums[left], nums[right] });
                        //进行去重
                        if (left < right && nums[left] == nums[left+1])  //这里不能left++
                        {
                            left++;
                        }
                        else if (left < right && nums[right] == nums[right-1])  
                        {
                            right--;
                        }
                    }

                    //找到答案 双指针收缩
                    left++;
                    right--;
                }
            }

            return result;
        }
}

细节还是比较多的。

tags: #算法