P3004. 跳房子II

解题思路

题目理解

注意，本题和 经典题型、三数之和 基本完全一致。区别仅仅在于本题需要找到 下标和最小 的索引。

首先要理解题意。输出描述的断句是这样的：返回 索引和最小（且）满足要求的步数组合。索引和 一词是一个整体，表示需要找到三个数的索引的总和。

数组排序

在 经典题型、三数之和 中我们知道，要使用 双指针算法，我们必须对原数组进行 从小到大的排序。但是在本题中，一旦对原数组进行排序，那么其原来的索引就丢失了。

因此，我们在排序的过程中，除了对已知数据 num 进行排序，还必须同时储存每一个元素在原输入数组 lst 中的索引 idx。故排序过程如下：

注意此处我们新建的 nums 是一个 二维数组，其中的内层元素 (num, idx) 是一个 二元组，其中 num 是元素值，idx 是 num 在原输入数组 lst 中的索引。nums 中元素的排序，会 先按照 `num` 的大小进行从小到大排序，当 num 相等时，则 按照其出现在 `lst` 中的索引 `idx` 进行从小到大排序。

譬如对于例子：

我们会得到：

双指针过程

接下来是非常经典的 双指针过程。

对于 nums 中的元素，我们遍历里面里面的每一组 (num, idx)（其在 nums 中的索引值为 i），将其固定为选择的 第一个元素。而剩余的 第二个元素 和 第三个元素，分别设置 left 和 right 从 i+1 和 n-1 的位置从两边往中间靠拢。

代码框架如下：

接下来就是填充双指针过程，即上述代码框架中的 while 循环。

我们令当前的三数之和为 sum3 = first + nums[left][0] + nums[right][0]。当：

• sum3 > target 时，三数之和太大，sum3 需要减小，right 左移
• sum3 < target 时，三数之和太小，sum3 需要增加，left 右移
• sum3 == target 时，此时所选择的三个数的和为题目输入的目标和 target，我们需要更新答案。同时 只有 `right` 左移。

关键讨论：为什么 sum3 == target 时只移动 right？

此处需要特别讨论，为什么在 sum3 == target 的时候，我们的代码中 只有 `right` 左移，而不是 left 右移或者 left 和 right 同时移动。

在 经典题型、三数之和 中，由于我们要找的是 元素组合，而不是元素的索引组合，因此我们无论写成 left 右移、right 左移还是 left 和 right 同时移动，答案都是正确的。

这三种写法，都能够避免 while 的死循环（也是这里指针移动的唯一作用）。这是因为，只需要保证 while 中的每一个 if 分支中，至少有一个指针是在变化的，那么 while 中的 left < right 条件就一定会有不成立的时候，会顺利退出循环。

但是在本题中，由于我们要找的是 元素的索引组合，并且要求是找到 索引和最小 的索引组合。可能会存在一种情况，即 nums[right-1][0] == nums[right][0]。由于当 num 相等时元素按照在原数组中的索引 idx 进行从小到大排序，此时必然存在 nums[right-1][1] < nums[right][1]。

譬如数组：

假设 target = 9，当 i = 1，left = 2，right = 5 时，我们已经找到了 (2, 0), (2, 2), (5, 3) 这三个元素它们的数字和为 target，索引和为 5。

由于 nums[4][0] == nums[5][0] == 5。如果此时我们移动了 left，我们将会错过索引和更小的 (2, 0), (2, 2), (5, 1) 这样的组合（i = 1，left = 2，right = 4，索引和为 3）。所以 当我们找到一组答案的时候，不能够移动 `left`（即使这样在其他题目中的正确的），只能移动 `right`。这样才能够尽可能地找到更小的索引和。

整体代码

因此，整体的代码如下：

复杂度分析 设数组长度为 n。

• 带下标排序：先构造 (num, idx) 二元组数组，O(n)；再按「数值优先、原下标其次」排序，O(n log n)。
• 主体是「固定第一个数 + 相向双指针」的两层结构：外层 for 枚举第一个数至多 n - 2 次；对每个固定的 i，内层 while 中 left 与 right 相向移动，合计至多 n 步。所以主体部分为 O(n²)，这是整个算法的瓶颈。
• 外层的剪枝（最小的三个候选数之和已超过 target 就 break）与去重（跳过与前一个相等的 first）能显著减少实际运算量，但不改变最坏情况的量级。
• 收尾对 ans_idx 排序只有固定 3 个元素，常数代价。

总时间复杂度为 O(n²)，空间复杂度为 O(n)，主要是带原始下标的排序副本 nums。