力扣刷题日常(15-16)

第15题: 三数之和 (难度:中等)

原题:

给我们一个整数数组 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

原题提示：

  1. So, we essentially need to find three numbers x, y, and z such that they add up to the given value. If we fix one of the numbers say x, we are left with the two-sum problem at hand!(所以，我们实际上需要找出三个数 x、y 和 z，使得它们的和等于给定的值。如果我们固定其中一个数，比如 x，那么就只剩下我们当前要解决的两个数相加的问题了！)
  2. For the two-sum problem, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?(对于“两数之和”问题，如果我们固定其中一个数字，比如 x，那么我们就必须遍历整个数组来找到下一个数字 y，其值为输入参数 value 减去 x。我们能否以某种方式改变数组，从而使这个搜索过程变得更加快捷呢？)
  3. The second train of thought for two-sum is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?(对于两数之和的第二种思路是，在不改变数组的情况下，我们能否以某种方式使用额外的空间？比如，或许可以使用哈希表来加快搜索速度？)

开始解题：

那么这是一道十分经典的算法问题, 它考察的不仅仅是暴力求解, 更是如何通过巧妙的思路优化时间和空间效率.

解决这个问题, 如果我们直接使用三层循环来遍历所有可能的三数组合, 时间复杂度会达到 O(n³), 这在 n 达到3000时是绝对无法接受的. 因此, 我们需要更优化的方法. 结合题目的提示, 核心思想是 “降维”, 也就是将一个 “三数之和” 的问题, 转化为我们更熟悉的 “两数之和” 问题.

那么我们这里选择的解法为 “排序 + 双指针”.

详细步骤如下所示:

  1. 特殊情况处理: 如果数组的长度小于3, 那么不可能凑成三元组, 直接返回一个空列表.

  2. 排序: 这是整个算法的关键第一步. 我们首先对整个数组进行升序排序. 排序有两个至关重要的作用:

    • 它为后续使用 “双指针” 技巧创造了前提.
    • 它能极大地简化 “去重” 的逻辑. 相同的元素会聚集在一起, 便于我们跳过.
    • 我们这里使用数组自带的排序方法, 时间复杂度记为 O(n log n)

  3. 固定一个数, 转化问题: 我们使用一个 for 循环来遍历排序后的数组, 假设当前遍历到的元素是 nums[i]. 我们将这个 nums[i] 作为三元组中的第一个固定的数. 那么, 我们的任务就变成了在数组剩下的部分 (从索引 i+1 到末尾) 中, 寻找另外两个数, 使它们的和等于 -nums[i]. 这就成功地将问题从 “三数之和” 变成了 “两数之和”.

  4. 双指针登场: 对于每一个固定的 nums[i], 我们在它后面的区间 [i+1, nums.length-1] 中寻找目标两数. 我们使用两个指针:

    • 左指针 left, 初始化为 i + 1.
    • 右指针 right, 初始化为数组的最后一个元素的索引 nums.length - 1.

  5. 移动指针并判断: 我们在 left < right 的条件下进行循环:

    • 计算三个数的当前和 sum = nums[i] + nums[left] + nums[right].
    • 如果 sum == 0: 恭喜, 我们找到了一个符合条件的三元组 [nums[i], nums[left], nums[right]]. 我们将它添加到结果列表中.
    • 如果 sum < 0: 说明总和太小了. 因为数组是排好序的, 为了让 sum 变大, 我们需要一个更大的数. 此时, 左指针 left 向右移动 (left++), 指向一个可能更大的值.
    • 如果 sum > 0: 说明总和太大了. 为了让 sum 变小, 我们需要一个更小的数. 此时, 右指针 right 向左移动 (right--), 指向一个可能更小的值.

  6. 处理重复三元组: 这是本题的另一个核心难点.

    • 对固定的数 nums[i] 去重: 在 for 循环中, 如果当前的 nums[i] 和它前一个数 nums[i-1] 相等, 说明以这个数开头的所有可能组合我们都已经找过了, 为了避免重复, 我们应该直接跳过, 继续下一次循环.
    • 对找到的结果 [nums[left], nums[right]] 去重: 当我们找到一个 sum == 0 的三元组后, 我们不能立刻停止. 比如数组是 [-2, 0, 0, 2, 2], i 指向 -2. left 指向第一个 0, right 指向最后一个 2, 和为0. 此时, 我们需要继续移动 left 和 right 来寻找新的组合. 但如果只是简单地 left++ 和 right--, left 会指向第二个 0, right 会指向第一个 2, 它们依然能组成和为0的三元组, 但这和我们刚找到的是重复的. 所以, 在找到一个解后, 我们需要持续移动 left 和 right 指针, 跳过所有与当前 nums[left] 和 nums[right] 相等的后续元素.

通过以上步骤, 我们就能在 O(n²) 的时间复杂度内, 找出所有不重复的三元组.

搭配代码理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Solution 
{
    public IList<IList<int>> ThreeSum(int[] nums) 
    {
        // 1. 初始化结果列表
        var result = new List<IList<int>>();

        // 2. 处理边界情况
        if (nums == null || nums.Length < 3) 
        {
            return result;
        }

        // 3. 对数组进行排序
        Array.Sort(nums);

        // 4. 主循环, 固定第一个数 nums[i]
        for (int i = 0; i < nums.Length - 2; i++) 
        {
            // 如果固定的数大于0, 因为数组已排序, 后面的数都大于0, 和不可能为0
            if (nums[i] > 0) 
            {
                break;
            }

            // 5. 对固定的数进行去重
            // 如果当前数字和前一个数字相同, 则跳过, 避免重复计算
            // 这里因为已经排序过了。所以直接和前面一个进行比较即可
            if (i > 0 && nums[i] == nums[i - 1]) 
            {
                continue;
            }

            // 6. 初始化双指针
            int left = i + 1;
            int right = nums.Length - 1;

            // 7. 双指针向中间移动
            while (left < right) 
            {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) 
                {
                    // 找到了一个解
                    result.Add(new List<int> { nums[i], nums[left], nums[right] });

                    // 8. 对左右指针指向的数进行去重
                    while (left < right && nums[left] == nums[left + 1]) 
                    {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) 
                    {
                        right--;
                    }

                    // 移动指针, 寻找新的可能性
                    left++;
                    right--;
                } 
                else if (sum < 0) 
                {
                    // 和太小, 左指针右移
                    left++;
                } 
                else // sum > 0
                {
                    // 和太大, 右指针左移
                    right--;
                }
            }
        }

        return result;
    }
}

简单补充：

  1. IList<IList<int>> (返回类型)
  • IList<T>: 这是一个接口 (Interface), List<T> 是它的一个常见实现. 在Unity中我们可能直接用 List<GameObject>, 这里的 IList 是一种更通用的"契约". 它规定了一个集合应该有哪些基本功能 (如 Add, Remove, Count), 但不关心具体是怎么实现的. 在函数签名中使用接口 (IList) 而不是具体类 (List) 是一个很好的编程习惯, 这让代码更灵活, 更具扩展性.
  • IList<IList<int>>: 这是一个 “列表的列表”. 外层的 IList 表示最终结果是一个列表, 而这个列表中的每一个元素 (IList<int>) 本身也是一个整数列表, 用来存放我们找到的每个三元组, 例如 [-1, 0, 1].
  1. Array.Sort(nums);
  • 这是.NET标准库中 System.Array 类提供的一个静态方法. 它会对传入的数组 nums 进行 原地排序 (in-place sort), 也就是说它会直接修改 nums 数组本身, 而不是返回一个排好序的新数组. 默认是升序排序.
  • C#的 Array.Sort 内部实现很复杂, 是一种名为 IntroSort 的混合排序算法, 但其平均和最坏情况下的时间复杂度都可以视为 O(n log n).

知识点总结:

  1. 降维思想: 这是解决复杂问题的一个核心策略. 当我们面对一个看似需要多层循环 (如三层, 四层) 的问题时, 优先思考是否能通过 “固定” 其中一个或多个变量, 将问题转化为一个更低维度, 我们更熟悉的问题. “三数之和” 通过固定一个数, 巧妙地变成了 “两数之和”. 这个思想是算法优化的金钥匙.
  2. 预处理的重要性: Array.Sort() 就是一个典型的预处理步骤. 有时, 在正式解决问题前, 花费一些时间对数据进行排序, 建立索引 (如哈希表), 或者进行其他形式的规整, 会为后续的算法执行创造极大的便利, 从而获得数量级上的性能提升. “先花一点时间磨刀, 可以大大缩短砍柴的时间”.
  3. 双指针算法模式: 对于一个 有序数组, 使用一头一尾两个指针相向而行, 是一个极其高效的模式. 它能将嵌套循环的 O(n²) 复杂度降低到线性 O(n). 这个模式广泛应用于查找特定和的数对, 反转数组, 去重等场景.
  4. 时间复杂度权衡: 优秀的工程师需要具备分析和权衡不同方案成本的能力. 在本例中, 我们接受了排序带来的 O(n log n) 成本, 是因为它帮助我们将查找成本从 O(n²) 降到了 O(n), 最终使得总复杂度从 O(n³) 优化到了 O(n²). 在评估一个多步骤算法的性能时, 要抓住其中的 主导项 (dominant term).

第16题: 最接近的三数之和 (难度:中等)

原题:

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

1
2
3
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2：

1
2
3
输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -104 <= target <= 104

开始解题:

那么这道题和上一道是十分相似, 唯一有变化的就是我们要判断的内容了, 在双指针移动的每一步, 我们都需要检查当前的 sum 是否比我们之前记录的"最接近的和"(我们用 result 来存储)更接近 target.

  • 比较距离: 我们不直接比较 sum 和 result, 而是比较它们与 target 的"距离". 这个距离就是差值的绝对值: Math.Abs(sum - target).
  • 更新: 如果 Math.Abs(sum - target) 小于 Math.Abs(result- target), 说明我们找到了一个更好的答案, 此时就更新 result = sum.

直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        // 1. 对数组进行排序, 这是双指针算法的前提.
        Array.Sort(nums);

        // 2. 初始化一个结果变量. 使用数组前三个数的和作为初始值,
        int result = nums[0] + nums[1] + nums[2];

        // 3. 遍历数组, 固定第一个数 nums[i].
        // 循环到倒数第三个数即可, 因为我们需要为 left 和 right 指针留出位置.
        for (int i = 0; i < nums.Length - 2; i++) {
            // 4. 跳过重复的起始元素.
            // 如果当前的元素和前一个相同, 那么以它为起点的搜索会和之前的重复, 直接跳过.
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 5. 初始化左右指针.
            int left = i + 1;
            int right = nums.Length - 1;

            // 6. 开始双指针循环.
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                // 7. 检查当前的和是否比已记录的结果更接近目标.
                if (Math.Abs(sum - target) < Math.Abs(result - target)) {
                    result = sum;
                }

                // 8. 根据 sum 和 target 的大小关系移动指针.
                if (sum < target) {
                    // 和太小, 需要增大, 所以移动左指针.
                    left++;
                } else if (sum > target) {
                    // 和太大, 需要减小, 所以移动右指针.
                    right--;
                } else {
                    // 和与目标完全相等, 已经是"最接近"(距离为0), 直接返回.
                    return sum;
                }
            }
        }

        // 9. 循环结束后, 返回记录的最接近的和.
        return result;
    }
}

但是这个代码在力扣上的表现我并不满意

image-20250805190637931

所以我们要继续进行优化.

我们当前的 O(n²) 方案在理论上已经是该问题的最优解法. 所以, 优化的空间在于剪枝 (Pruning), 即在循环过程中, 提前识别出那些不可能产生更优解的分支, 并直接跳过它们.

优化的核心: 剪枝策略

优化点 1: 对外层循环进行剪枝 (最重要)

逻辑:
当我们固定了 nums[i] 后, 我们能构成的最小的和是 nums[i] + nums[i+1] + nums[i+2].(因为我们已经排序)
如果这个可能的最小和都已经比我们当前找到的 result 更远离 target (并且是在 target 的右侧), 那么后续的 i (只会让这个最小和变得更大) 就完全没有必要再检查了. 我们可以直接 break 掉整个外层循环.

优化点 2: 对内层循环进行剪枝 (处理重复元素)

逻辑:
在 while 循环中, 当我们移动了 left 或 right 指针后, 如果新位置的元素和旧位置的元素相同, 那么计算出的 sum 也将是相同的, 这是一次无效的重复计算. 我们应该跳过所有这些重复的元素.

补充:

那么这个其实在上一道题里用到了, 不过为什么我在这道题里没用到呢, 原因很简单, 我放错位置, 然后报错了, 然后我就直接删除了.

那么我们最后的代码就是这样的了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);
        int result = nums[0] + nums[1] + nums[2];
        int minDiff = Math.Abs(result - target);

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

            // 【优化1】: 剪枝, 如果最小可能和都比当前最优解差, 直接退出
            int minPossibleSum = nums[i] + nums[i + 1] + nums[i + 2];
            if (minPossibleSum > target && minPossibleSum - target >= minDiff) {
                break;
            }
          
            // 【优化1.1】: 剪枝, 如果最大可能和都比当前最优解差, 跳过本次循环
            int maxPossibleSum = nums[i] + nums[nums.Length - 2] + nums[nums.Length - 1];
            if (maxPossibleSum < target && target - maxPossibleSum >= minDiff) {
                continue;
            }

            int left = i + 1;
            int right = nums.Length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int diff = Math.Abs(sum - target);

                if (diff < minDiff) {
                    minDiff = diff;
                    result = sum;
                }

                if (sum < target) {
                    left++;
                    // 【优化2】: 跳过内部重复
                    while (left < right && nums[left] == nums[left - 1]) left++;
                } else if (sum > target) {
                    right--;
                    // 【优化2】: 跳过内部重复
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else {
                    return sum; // 距离为0, 最优解
                }
            }
        }
        return result;
    }
}

image-20250805191249985

现在的质量已经很好了, 我们不再进行研究了, 因为我们不为了算法竞赛, 而是为了实际应用.

知识点总结:

剪枝优化

  • 核心思想: 在搜索或遍历的过程中, 利用已知信息(如数组的有序性), 提前判断某些分支或路径不可能产生最优解, 从而"剪掉"这些分支, 避免无效的计算.
  • 启示: 优化不仅仅是降低算法的时间复杂度, 也包括在同等复杂度下减少实际的运算量. "剪枝"是性能优化的关键技巧, 特别是在处理大数据集或复杂搜索问题(如AI, 游戏寻路)时.