Leecode[15] 三数之和

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

• 先排序。
• 特判，集合为空，元素个数小于3、第一个元素大于0。
• 去重，当前元素值与上一个元素值相同，则跳过。
• 双指针，左指针指向 i+1，右指针指向 nums.Length - 1。

private static List<Tuple<int, int, int>> Method(int[] nums)
{
    var ans = new List<Tuple<int, int, int>>();
    if (nums == null || nums.Length < 3)
    {
        return ans;
    }

    Array.Sort(nums); // O(nlogn)

    for (int i = 0; i < nums.Length - 2; i++)
    {
        if (nums[i] > 0)
        {
            break;
        }

        // 去掉重复情况
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue;
        }

        int target = -nums[i];
        int left = i + 1, right = nums.Length - 1;
        while (left < right)  // 双指针遍历 O(n)
        {
            if (target == nums[left] + nums[right])
            {
                ans.Add(new Tuple<int, int, int>(nums[i], nums[left], nums[right]));

                // 双指针内缩
                left++;
                right--;

                // 去重复
                while (left < right && nums[left] == nums[left - 1])
                {
                    left++;
                }

                while (left < right && nums[right] == nums[right - 1])
                {
                    right--;
                }
            }
            else if (target > nums[left] + nums[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
    }

    return ans;
}