寻找两数组中差值等于target的元素索引（要求时间复杂度O(n)）

问题描述 #

给定两个元素互不重复的整数数组 numsfirst 和 numssecond，以及目标值 target，需找到满足 numssecond[j] - numsfirst[i] = target 的索引对 [i, j]；若不存在符合条件的元素对，返回 [-1, -1]。

示例 #

• 示例1：输入 numsfirst = [3,4,10]，numssecond = [1,4,8]，target = 5，输出 [0,2]（因 8 - 3 = 5）
• 示例2：输入 numsfirst = [2,4,10]，numssecond = [1,4,8]，target = 5，输出 [-1,-1]

解法思路 #

要实现O(n)的时间复杂度，核心是用哈希表（字典）存储数组元素与索引的映射，将查找操作从O(n)降至O(1)，具体步骤：

1. 遍历 numsfirst，将每个元素作为键、对应索引作为值存入哈希表；
2. 遍历 numssecond，对每个元素 num，计算需要匹配的 numsfirst 元素：required = num - target；
3. 检查 required 是否存在于哈希表中：
   • 若存在，直接返回 [哈希表[required], 当前索引j]；
   • 若遍历结束仍未找到，返回 [-1,-1]。

代码实现（Python） #

def find_index_pair(numsfirst, numssecond, target):
    num_index_map = {num: idx for idx, num in enumerate(numsfirst)}
    for j, num in enumerate(numssecond):
        required = num - target
        if required in num_index_map:
            return [num_index_map[required], j]
    return [-1, -1]

复杂度说明 #

• 时间复杂度：O(m + n)，其中m是numsfirst的长度，n是numssecond的长度，两次遍历均为线性时间，哈希表查找为O(1)；
• 空间复杂度：O(m)，用于存储numsfirst的元素-索引映射。

示例验证 #

• 示例1运行：numsfirst的哈希表为{3:0,4:1,10:2}，遍历到numssecond的元素8时，required = 8 - 5 = 3，存在于哈希表中，返回[0,2]；
• 示例2运行：遍历numssecond的所有元素，计算出的required分别为-4、-1、3，均不在numsfirst的哈希表中，返回[-1,-1]。

内容的提问来源于stack exchange，提问作者Sandeep Maurya