P2811. 跳房子I

解题思路

注意，本题和 经典题型、两数之和 几乎完全一致。区别在于需要输出 索引和最小的两个数字。

本题关于哈希表的部分已经强调过很多遍了，因此不再花费篇幅进行介绍。所以本篇题解主要介绍一些同学们在这一道题里面比较困惑的一些细节处理上的问题。

输入与输出

本题的输入与其他很多题目不同的地方在于，输入的字符串虽然能够表示一个数组，但是其前后包含了中括号 "[]"。如果我们想要根据逗号 "," 对原字符串进行切割的话，会得到第一个元素和最后一个元素分别包含 "[" 和 "]"。

为了避免这种情况，我们可以对 input() 得到的字符串利用切片进行掐头去尾的操作，即：

再结合内置函数 map() 和方法 split()，我们可以得到数字列表 nums：

同理，本题答案的输出也需要包含中括号 "[]"。假设最终答案数组 ans = [0, 1]，如果我们直接输出 ans，即：

会得到以下输出：

注意到逗号 "," 的后面包含空格 " " 的。但这是 错误的输出结果，会得 0 分！仔细观察题目要求的输出，逗号后面不应该包含空格。正确的输出应该是：

为了能够正确得到上述结果，我们不得不使用 格式化字符串 的方式进行输出，即：

这再一次提醒我们（在其他题目中也有所体现），ACM 模式的判题机制是相当严格的。题目要求你的答案输出和期望答案输出完全一致。多一个空格少一个空格，中英文标点符号不分，都会导致整道题目直接得 0 分。

索引和最小值的初始值设置

本题和 经典题型、两数之和 最大的区别在于，本题可能存在多组和为 target 的数对。题目要求我们需要输出 索引和最小的两个数字。所以我们必须在原版题目的基础上加上这个过程。

首先我们考虑一个非常简单的问题。如果要求我们在不使用内置函数 min() 和 max() 的前提下，找到一个数组 nums 中的最小值，我们会如何做？

这个问题非常简单，我们可以这样完成：设置一个初始值 ans 表示数组中可能的最小值。用循环遍历整个数组 nums，如果发现某个数字 num 比初始值更小的时候，则我们将 ans 替换为这个数字。退出循环后，最终的 ans 即为答案。

在初始化 ans 的时候，我们有两种策略：

• ans 越大越好，必须要大过 nums 中的最小值。所以可以设置 ans = inf。
• ans 是一个可能的答案。数组中的每一个元素都是可能的答案，所以可以设置 ans = nums[0]。

回到这道题本身，我们要找到索引和最小的两个数字，可以设置一个变量 min_idx_sum 来表示这个索引和。那么很多同学困惑的地方在于，下面的代码为什么是这样初始化变量 min_idx_sum 的：

由于后面我们希望能够找到更小的索引和，所以我们可以把 min_idx_sum 初始化为一个 较大值。显然，对于长度 n = len(nums) 而言的数组，最大的两个索引是 n-1 和 n-2，它们的和小于 n*2。当我们设置 min_idx_sum 的初始值为 len(nums)*2 时，其实跟设置 inf 或者 len(nums)*2-2 是一样的。

PS：在此我也希望大家能够举一反三。如果某个题目问的是寻找最大值且元素都是正数的话，那么我们就可以设置 ans 初始值为 0 或者 -inf 了。一定要学会变通。

寻找索引和最小值

接下来的任务就是，如何把索引和最小值的问题，加入到经典题目 经典题型、两数之和 中。

如果不加限制，其算法过程如下： 1. 遍历 nums 的每一个索引 i 和对应的数字 num 2. 计算剩余数字 rest_num = target - num 是否位于哈希表 hash_dic 中，若在则得到答案 ans 3. 将当前数字 num 作为 key，当前索引 i 作为 value，将键值对 (num, i) 储存入哈希表 hash_dic 中

其代码如下：

但由于我们希望寻找到的是 索引和最小值。假设在原数组中存在两个相同的数字，我们在哈希表中储存的索引 i，必然希望它是更早出现的那个而不是更晚出现的那个。所以在更新哈希表的时候，需要额外多加一个判断：如果 num 已经位于哈希表中了，则不进行更新。修改后代码如下：

另外，只有当当前两数索引和，小于全局索引和的时候，我们才需要更新答案 ans。当前数字 num 的索引为 i，剩余数字 rest_num 的索引为 hash_dic[rest_num]。故修改后代码如下：

特别注意，当 min_idx_sum > hash_dic[rest_num] + i 成立后，既要修改答案列表 ans，也要修改全局的索引最小和 min_idx_sum 为当前更新的 hash_dic[rest_num] + i。

综上就构成了本题的核心算法逻辑了。

不能在第一次找到答案就退出

在和同学们交流的过程中，有同学提出了以下解法：

即在第一次找到符合要求的答案时就退出。同学的理由非常简单，由于遍历是从左到右进行的，那么找到的第一组自然就是索引和最小的情况。但这是一个 比较典型的、过于想当然的思路。

我们可以非常容易地举出反例。考虑例子：

显然有两组索引 [0, 4] 和 [2, 3]（注意是索引而非元素本身）能使得 nums 中对应的两个数的和为 target。如果是从左往右遍历，我们会先找到索引对 [2, 3]，但显然 [2, 3] 的和会小于 [0, 4]。一旦在找到 [2, 3] 时就提前退出，那么将找不到正确结果 [0, 4]。

复杂度分析

设步数数组 nums 的长度为 n。

算法主体是一趟遍历：对每个元素 num 计算 rest_num = target - num，到哈希表 hash_dic 中做一次查询；命中时比较并可能更新 min_idx_sum 与 ans，是常数次操作；num 未收录过时再做一次 O(1) 的写入。注意本题不能在第一次找到配对时 break（正文已用反例说明），必须完整扫完整个数组才能确认索引和最小的组合，所以循环恒定执行 n 轮，时间复杂度为 O(n)。

空间上，哈希表只为每种不同的步数记录首次出现的下标，最坏情况下所有步数互不相同，额外空间为 O(n)。

作为对照，暴力枚举所有下标对 (i, j) 再从中取索引和最小者是 O(n^2)；哈希表版本用“数值对应首次出现下标”的一份记录，把找配对压缩成每步一次平均 O(1) 的查询，这与经典的两数之和是同一份收益。