如何在O(n)时空复杂度下找到数组中元素差等于位置差的两个索引

首先把问题的核心条件做数学变形，这是解决问题的关键：

我们需要找到i<j，满足|A[i] - A[j]| = j - i。把绝对值拆开，得到两种等价情况：

• 情况1：A[i] - A[j] = j - i，移项后可得 A[i] + i = A[j] + j
• 情况2：A[j] - A[i] = j - i，移项后可得 A[i] - i = A[j] - j

换句话说，只要存在两个不同的索引，它们的A[i]+i值相等，或者A[i]-i值相等，就符合题目要求。

具体实现步骤 #

用两个哈希表（字典）来记录每个派生值第一次出现的索引，遍历数组时实时检查：

• 初始化两个空字典，比如plus_map（存A[i]+i到索引的映射）和minus_map（存A[i]-i到索引的映射）
• 遍历数组的每个元素，索引记为i，元素值为num：
  1. 计算current_plus = num + i：
     • 如果current_plus已经在plus_map里，那么plus_map[current_plus]和i就是满足条件的一对索引（先存的索引一定小于当前i），直接返回这两个索引。
     • 如果不在，就把current_plus: i存入plus_map。
  2. 计算current_minus = num - i：
     • 如果current_minus已经在minus_map里，那么minus_map[current_minus]和i就是满足条件的一对索引，直接返回。
     • 如果不在，就把current_minus: i存入minus_map。
• 如果遍历完整个数组都没找到符合条件的索引对，说明不存在这样的数对。

复杂度分析 #

• 时间复杂度：每个元素只遍历一次，哈希表的插入和查询操作平均时间复杂度是O(1)，整体时间复杂度为O(n)。
• 空间复杂度：两个哈希表最多各存储n个键值对，整体空间复杂度为O(n)，完全符合题目要求。

为什么你的之前方法没凑效？ #

你之前尝试的基数排序+双指针思路绕了弯路，问题的核心不是排序，而是通过数学变形把“绝对值差等于索引差”转化为“找重复的派生值”，用哈希表就能直接高效解决。

内容的提问来源于stack exchange，提问作者Yara Halloun