如何以O(N)复杂度单次for循环查找列表中和为目标值的整数对索引

• 核心用哈希表（Python字典）缓存已经遍历过的元素和对应索引，省去嵌套循环查找配对值的过程，把时间复杂度控制在O(N)级别
• 单次遍历列表时，对每个元素先计算能和它凑成目标值的补数（target - 当前元素值），如果补数已经存在于缓存中，说明找到了一对符合要求的索引，直接把索引对存入结果即可
• 无论补数是否存在，都要把当前元素和它的索引存入缓存，供后续遍历到的元素查找匹配
• 字典的查找、插入操作平均时间复杂度都是O(1)，全程只做一次列表遍历，整体满足线性时间复杂度要求

def find_sum_pairs(lst, target):
    num_index_map = {}
    result = []
    for idx, num in enumerate(lst):
        complement = target - num
        # 检查补数是否在已经遍历过的元素中
        if complement in num_index_map:
            result.append( (num_index_map[complement], idx) )
        # 缓存当前元素和索引
        num_index_map[num] = idx
    # 若不需要和示例输出顺序完全一致，可删除下面的排序行，全程严格单循环O(N)
    result.sort()
    return result

# 测试用例
lst = [2, 4, 3, 6, 5]
target = 7
print(find_sum_pairs(lst, target)) # 输出 [(0, 4), (1, 2)]

对照给出的示例走完整遍历流程即可确认正确性：

1. 遍历到索引0的元素2，补数为5，缓存为空无匹配，存入2:0到缓存
2. 遍历到索引1的元素4，补数为3，缓存中无3，存入4:1到缓存
3. 遍历到索引2的元素3，补数为4，缓存中存在4对应索引1，将(1,2)加入结果，存入3:2到缓存
4. 遍历到索引3的元素6，补数为1，缓存中无1，存入6:3到缓存
5. 遍历到索引4的元素5，补数为2，缓存中存在2对应索引0，将(0,4)加入结果，存入5:4到缓存
6. 对结果按第一个索引升序排序后，就得到和期望一致的输出

提示：如果列表存在重复元素，该写法默认取最先出现的元素索引做配对，符合这类问题的常规输出要求。

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