15.三数之和

LeetCode LeetCode 数组 热题100 双指针 排序
发布时间 :
字数:3.6k 阅读 : 评论:
  1. 15.三数之和
    1. 15.1 题目
    2. 15.2 题解
      1. 方法一：暴力枚举三元组
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：双指针法
        1. 思路
        2. 复杂度分析
        3. 代码
    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。

具体步骤：

  1. 先对数组排序，方便跳过重复元素。
  2. 第一层循环固定第一个数 nums[i]，如果与前一个元素相同则跳过。
  3. 第二层循环固定第二个数 nums[j]，如果与前一个元素相同则跳过。
  4. 第三层循环遍历第三个数 nums[k]，如果与前一个元素相同则跳过。
  5. 计算三数之和，等于 0 则加入结果集；大于 0 则提前终止（因为数组有序）。

举例：对于 nums = [-1,0,1,2,-1,-4]，排序后为 [-4,-1,-1,0,1,2]。

  • 当 i=1, j=2, k=4 时，nums[i]=-1, nums[j]=-1, nums[k]=1，和为 -1，继续。
  • 当 i=1, j=3, k=5 时，nums[i]=-1, nums[j]=0, nums[k]=2，和为 1，继续。
  • 当 i=1, j=2, k=5 时，-1 + (-1) + 2 = 0，得到 [-1,-1,2]；当 i=1, j=3, k=4 时，-1 + 0 + 1 = 0，得到 [-1,0,1]（下标与排序后数组对齐）。

注意：此方法时间复杂度高，会超时，仅作为思路参考。

复杂度分析

  • 时间复杂度：O(n^3)，三层循环。
  • 空间复杂度：O(1)，不考虑结果存储。

代码

// 方法一：暴力枚举三元组 会超时
// 三层循环判断是否加起来为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;
}

方法二：双指针法

思路

先对数组排序，然后固定一个数 nums[i]，用双指针在 i 的右侧查找两数之和等于 -nums[i]。

核心思想：将「三数之和为 0」转化为「两数之和为某个目标值」。

具体步骤：

  1. 对数组排序，便于去重和双指针移动。
  2. 遍历数组，固定第一个数 nums[i]：
    • 如果 nums[i] > 0，由于数组有序，后面的数都大于 0，三数之和不可能为 0，直接退出。
    • 如果 nums[i] 与前一个元素相同，跳过以避免重复三元组。
  3. 用左右指针 left 和 right 在 i 的右侧查找：
    • 计算 sum = nums[i] + nums[left] + nums[right]
    • 如果 sum > 0，说明右边的数太大，right--
    • 如果 sum < 0，说明左边的数太小，left++
    • 如果 sum == 0，找到一组解，记录后同时移动两个指针，并跳过重复元素

举例：对于 nums = [-1,0,1,2,-1,-4]，排序后为 [-4,-1,-1,0,1,2]。

  • 固定 i=1，nums[i]=-1，目标是找两数之和为 1。
    • left=2, right=5：-1 + (-1) + 2 = 0 ✓，记录 [-1,-1,2]
    • 移动指针继续，left=3, right=4：-1 + 0 + 1 = 0 ✓，记录 [-1,0,1]
  • 固定 i=2，nums[2]=-1 与 nums[1]=-1 相同，跳过避免重复。

复杂度分析

  • 时间复杂度：O(n^2)，外层循环 O(n)，内层双指针 O(n)。
  • 空间复杂度：O(1)，不考虑结果存储。

代码

// 方法二：双指针法
// 对输入的整数数组进行排序。方便后续双指针的移动，并且排序后相同的元素会在一起，有助于避免重复计算。
// 固定一个数字（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-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏