是否存在O(n)时间复杂度的方法查找数组中指定数值的所有对应索引

存在满足要求的实现方案，仅需单次线性遍历配合哈希表即可完成，时间复杂度严格控制在O(n)范围内。

需求回顾 #

• 查找数组 new int[]{2, 1, 3, 1, 4, 2, 1, 3} 中各数值的所有索引
• 时间复杂度不超过 O(n)

实现思路 #

1. 初始化一个哈希映射（字典）结构，键为数组中的数值，值为存储对应索引的动态列表
2. 按顺序遍历数组的每一个元素，同步记录当前下标：
   • 若当前数值不在哈希映射中，先以该数值为键新建一个空列表作为对应值
   • 将当前下标追加到该数值对应的列表末尾
3. 遍历完成后，哈希映射中就存储了所有数值对应的全部索引，直接查询即可获取目标结果

代码实现（Java版） #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class IndexQuery {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 1, 3, 1, 4, 2, 1, 3};
        Map<Integer, List<Integer>> numIndexMap = new HashMap<>();

        // 单次遍历 时间复杂度O(n)
        for (int i = 0; i < arr.length; i++) {
            int currentNum = arr[i];
            numIndexMap.computeIfAbsent(currentNum, key -> new ArrayList<>()).add(i);
        }

        // 输出验证结果，和示例一致
        numIndexMap.forEach((num, indices) -> {
            System.out.printf("数值%d对应的索引为%s%n", num, indices);
        });
    }
}

复杂度说明 #

• 时间复杂度：仅遍历数组1次，哈希表的插入、查询均为O(1)均摊复杂度，整体复杂度为O(n)，n为数组长度
• 空间复杂度：需要额外存储所有数值对应的索引，最坏情况所有元素互不重复，空间占用为O(n)

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