当前位置：首页 > news >正文

力扣刷题日常(15-16)

news 2025/8/6 9:16:56

力扣刷题日常(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：

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

原题提示：

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，那么就只剩下我们当前要解决的两个数相加的问题了！)
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。我们能否以某种方式改变数组，从而使这个搜索过程变得更加快捷呢？)
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时是绝对无法接受的. 因此, 我们需要更优化的方法. 结合题目的提示, 核心思想是 “降维”, 也就是将一个 “三数之和” 的问题, 转化为我们更熟悉的 “两数之和” 问题.

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

详细步骤如下所示:

特殊情况处理: 如果数组的长度小于3, 那么不可能凑成三元组, 直接返回一个空列表.
排序: 这是整个算法的关键第一步. 我们首先对整个数组进行升序排序. 排序有两个至关重要的作用:
- 它为后续使用 “双指针” 技巧创造了前提.
- 它能极大地简化 “去重” 的逻辑. 相同的元素会聚集在一起, 便于我们跳过.
- 我们这里使用数组自带的排序方法, 时间复杂度记为 O(n log n)
固定一个数, 转化问题: 我们使用一个 for 循环来遍历排序后的数组, 假设当前遍历到的元素是 nums[i]. 我们将这个 nums[i] 作为三元组中的第一个固定的数. 那么, 我们的任务就变成了在数组剩下的部分 (从索引 i+1 到末尾) 中, 寻找另外两个数, 使它们的和等于 -nums[i]. 这就成功地将问题从 “三数之和” 变成了 “两数之和”.
双指针登场: 对于每一个固定的 nums[i], 我们在它后面的区间 [i+1, nums.length-1] 中寻找目标两数. 我们使用两个指针:
- 左指针 left, 初始化为 i + 1.
- 右指针 right, 初始化为数组的最后一个元素的索引 nums.length - 1.
移动指针并判断: 我们在 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--), 指向一个可能更小的值.
处理重复三元组: 这是本题的另一个核心难点.
- 对固定的数 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²) 的时间复杂度内, 找出所有不重复的三元组.

搭配代码理解:

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, 和不可能为0if (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;}
}

简单补充：

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].

Array.Sort(nums);

这是.NET标准库中 System.Array 类提供的一个静态方法. 它会对传入的数组 nums 进行 原地排序 (in-place sort), 也就是说它会直接修改 nums 数组本身, 而不是返回一个排好序的新数组. 默认是升序排序.
C#的 Array.Sort 内部实现很复杂, 是一种名为 IntroSort 的混合排序算法, 但其平均和最坏情况下的时间复杂度都可以视为 O(n log n).

知识点总结:

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

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

原题:

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

返回这三个数的和。

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

示例 1：

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

示例 2：

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

直接上代码:

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;}
}

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

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

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

优化的核心: 剪枝策略

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

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

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

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

补充:

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

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

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;}
}

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

知识点总结:

剪枝优化

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

查看全文

http://www.lryc.cn/news/610833.html