15.三数之和

LeetCode LeetCode 数组 排序 双指针
发布时间 :
字数:2.9k 阅读 : 评论:
  1. 15.三数之和
    1. 15.1 题目
    2. 15.2 题解
      1. 暴力枚举三元组
      2. 双指针法
    3. 15.3 代码
    4. 15.4 运行结果

15.三数之和

15.1 题目

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

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

示例：

  • 示例 1：

    • 输入：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：

    • 输入：nums = [0,1,1]
    • 输出：[]
    • 解释：唯一可能的三元组和不为 0。

  • 示例 3：

    • 输入：nums = [0,0,0]
    • 输出：[[0,0,0]]
    • 解释：唯一可能的三元组和为 0。

提示：

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

15.2 题解

暴力枚举三元组

// 方法一：暴力枚举三元组 会超时
// 三层循环判断是否加起来为0，可以先排序遇到相同的跳过提高效率
static IList<IList<int>> ThreeSum1(int[] nums)
{
    // 用于存储符合条件的三元组
    List<IList<int>> result = new List<IList<int>>();

    // 对数组进行排序，方便后续避免重复的数字
    Array.Sort(nums);

    // 使用三重循环枚举所有可能的三元组
    for (int i = 0; i < nums.Length - 2; i++)
    {
        // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
        if (i > 0 && nums[i] == nums[i - 1])
            continue;

        for (int j = i + 1; j < nums.Length - 1; j++)
        {
            // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;

            for (int k = j + 1; k < nums.Length; k++)
            {
                // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
                if (k > j + 1 && nums[k] == nums[k - 1])
                    continue;

                // 计算当前三个数字的和
                int sum = nums[i] + nums[j] + nums[k];

                // 判断是否满足条件，如果和为零，则添加到结果集
                if (sum == 0)
                {
                    result.Add(new List<int> { nums[i], nums[j], nums[k] });
                }
                else if (sum > 0)
                {
                    // 因为数组已排序，如果和大于零，减小k，提高下一轮循环的效率
                    break;
                }
            }
        }
    }

    // 返回符合条件的三元组集合
    return result;
}

双指针法

// 方法二：双指针法
// 对输入的整数数组进行排序。方便后续双指针的移动，并且排序后相同的元素会在一起，有助于避免重复计算。
// 固定一个数字（i 指针），然后使用两个指针（left 和 right）在 i 的右侧进行查找。

// 注意排重
// i 指针大于0时，由于数组已排序，后面的数字必然也大于0，直接跳出循环
// 如果i 指针与i-1所指向的元素相同，跳过此次循环

// 双指针循环查找的过程中，比较当前三个数字的和 sum 与 0 的关系，分为以下三种情况：
// 如果 sum > 0，说明右侧的数字过大，需要减小 right 指针。
// 如果 sum < 0，说明左侧的数字过小，需要增大 left 指针。
// 如果 sum == 0，说明找到一个符合条件的三元组，将其添加到结果集中，并移动左右指针以避免重复。如果左右指针下一元素相同可以跳过。
static IList<IList<int>> ThreeSum2(int[] nums)
{
    // 用于存储符合条件的三元组
    IList<IList<int>> result = new List<IList<int>>();

    // 对数组进行排序，方便后续处理
    Array.Sort(nums);

    // 遍历数组，注意到循环的终止条件是 nums.Length - 2，以确保有足够的元素形成三元组
    for (int nowKey = 0; nowKey < nums.Length - 2; nowKey++)
    {
        // 获取当前位置的数字
        int nowValue = nums[nowKey];

        // 如果当前数字大于0，由于数组已排序，后面的数字必然也大于0，直接跳出循环
        if (nowValue > 0)
            break;

        // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
        if (nowKey > 0 && nowValue == nums[nowKey - 1])
            continue;

        // 初始化左右指针
        int leftKey = nowKey + 1;
        int rightKey = nums.Length - 1;

        // 在左右指针之间执行查找
        while (leftKey < rightKey)
        {
            // 计算当前三个数字的和
            int sum = nowValue + nums[leftKey] + nums[rightKey];

            // 根据和的大小进行移动指针的操作
            if (sum > 0)
            {
                rightKey--;
            }
            else if (sum < 0)
            {
                leftKey++;
            }
            else
            {
                // 如果和为0，则将当前三个数字添加到结果集
                result.Add(new List<int> { nowValue, nums[leftKey], nums[rightKey] });

                // 移动左指针并跳过重复元素
                while (leftKey < rightKey && nums[leftKey] == nums[leftKey + 1])
                {
                    leftKey++;
                }

                // 移动右指针并跳过重复元素
                while (leftKey < rightKey && nums[rightKey] == nums[rightKey - 1])
                {
                    rightKey--;
                }

                //不是重复的再移动下
                leftKey++;
                rightKey--;
            }
        }
    }

    // 返回符合条件的三元组集合
    return result;
}

15.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，
        // 同时还满足 nums[i] + nums[j] + nums[k] == 0。
        // 请你返回所有和为 0 且不重复的三元组。

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

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

        // 示例 3：
        // 输入：nums = [0,0,0]
        // 输出：[[0,0,0]]
        // 解释：唯一可能的三元组和为 0。

        // 提示：
        // 3 <= nums.length <= 3000
        // -105 <= nums[i] <= 105

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { -1, 0, 1, 2, -1, -4 };
        IList<IList<int>> result1 = ThreeSum1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{FormatResult(result1)}");
        IList<IList<int>> result1_2 = ThreeSum2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{FormatResult(result1_2)}");

        // 示例 2
        int[] nums2 = { 0, 1, 1 };
        IList<IList<int>> result2 = ThreeSum1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{FormatResult(result2)}");
        IList<IList<int>> result2_2 = ThreeSum2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{FormatResult(result2_2)}");

        // 示例 3
        int[] nums3 = { 0, 0, 0 };
        IList<IList<int>> result3 = ThreeSum1(nums3);
        Console.WriteLine($"示例3 方法1 输出：{FormatResult(result3)}");
        IList<IList<int>> result3_2 = ThreeSum2(nums3);
        Console.WriteLine($"示例3 方法2 输出：{FormatResult(result3_2)}");

        #endregion
    }

    #region 答案

    // 方法一：暴力枚举三元组 会超时
    // 三层循环判断是否加起来为0，可以先排序遇到相同的跳过提高效率
    static IList<IList<int>> ThreeSum1(int[] nums)
    {
        // 用于存储符合条件的三元组
        List<IList<int>> result = new List<IList<int>>();

        // 对数组进行排序，方便后续避免重复的数字
        Array.Sort(nums);

        // 使用三重循环枚举所有可能的三元组
        for (int i = 0; i < nums.Length - 2; i++)
        {
            // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            for (int j = i + 1; j < nums.Length - 1; j++)
            {
                // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;

                for (int k = j + 1; k < nums.Length; k++)
                {
                    // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
                    if (k > j + 1 && nums[k] == nums[k - 1])
                        continue;

                    // 计算当前三个数字的和
                    int sum = nums[i] + nums[j] + nums[k];

                    // 判断是否满足条件，如果和为零，则添加到结果集
                    if (sum == 0)
                    {
                        result.Add(new List<int> { nums[i], nums[j], nums[k] });
                    }
                    else if (sum > 0)
                    {
                        // 因为数组已排序，如果和大于零，减小k，提高下一轮循环的效率
                        break;
                    }
                }
            }
        }

        // 返回符合条件的三元组集合
        return result;
    }


    // 方法二：双指针法
    // 对输入的整数数组进行排序。方便后续双指针的移动，并且排序后相同的元素会在一起，有助于避免重复计算。
    // 固定一个数字（i 指针），然后使用两个指针（left 和 right）在 i 的右侧进行查找。

    // 注意排重
    // i 指针大于0时，由于数组已排序，后面的数字必然也大于0，直接跳出循环
    // 如果i 指针与i-1所指向的元素相同，跳过此次循环

    // 双指针循环查找的过程中，比较当前三个数字的和 sum 与 0 的关系，分为以下三种情况：
    // 如果 sum > 0，说明右侧的数字过大，需要减小 right 指针。
    // 如果 sum < 0，说明左侧的数字过小，需要增大 left 指针。
    // 如果 sum == 0，说明找到一个符合条件的三元组，将其添加到结果集中，并移动左右指针以避免重复。如果左右指针下一元素相同可以跳过。
    static IList<IList<int>> ThreeSum2(int[] nums)
    {
        // 用于存储符合条件的三元组
        IList<IList<int>> result = new List<IList<int>>();

        // 对数组进行排序，方便后续处理
        Array.Sort(nums);

        // 遍历数组，注意到循环的终止条件是 nums.Length - 2，以确保有足够的元素形成三元组
        for (int nowKey = 0; nowKey < nums.Length - 2; nowKey++)
        {
            // 获取当前位置的数字
            int nowValue = nums[nowKey];

            // 如果当前数字大于0，由于数组已排序，后面的数字必然也大于0，直接跳出循环
            if (nowValue > 0)
                break;

            // 避免重复的数字，如果当前数字与前一个相同，跳过此次循环
            if (nowKey > 0 && nowValue == nums[nowKey - 1])
                continue;

            // 初始化左右指针
            int leftKey = nowKey + 1;
            int rightKey = nums.Length - 1;

            // 在左右指针之间执行查找
            while (leftKey < rightKey)
            {
                // 计算当前三个数字的和
                int sum = nowValue + nums[leftKey] + nums[rightKey];

                // 根据和的大小进行移动指针的操作
                if (sum > 0)
                {
                    rightKey--;
                }
                else if (sum < 0)
                {
                    leftKey++;
                }
                else
                {
                    // 如果和为0，则将当前三个数字添加到结果集
                    result.Add(new List<int> { nowValue, nums[leftKey], nums[rightKey] });

                    // 移动左指针并跳过重复元素
                    while (leftKey < rightKey && nums[leftKey] == nums[leftKey + 1])
                    {
                        leftKey++;
                    }

                    // 移动右指针并跳过重复元素
                    while (leftKey < rightKey && nums[rightKey] == nums[rightKey - 1])
                    {
                        rightKey--;
                    }

                    //不是重复的再移动下
                    leftKey++;
                    rightKey--;
                }
            }
        }

        // 返回符合条件的三元组集合
        return result;
    }

    #endregion

    #region 辅助方法

    // 格式化结果为字符串
    static string FormatResult(IList<IList<int>> result)
    {
        if (result.Count == 0)
            return "[]";

        List<string> formattedResults = new List<string>();

        foreach (var list in result)
        {
            formattedResults.Add($"[{string.Join(", ", list)}]");
        }

        return $"[{string.Join(", ", formattedResults)}]";
    }

    #endregion
}

15.4 运行结果

示例1 方法1 输出：[[-1, -1, 2], [-1, 0, 1]]
示例1 方法2 输出：[[-1, -1, 2], [-1, 0, 1]]
示例2 方法1 输出：[]
示例2 方法2 输出：[]
示例3 方法1 输出：[[0, 0, 0]]
示例3 方法2 输出：[[0, 0, 0]]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏