如何优化IndexOfAll方法的算法以提升性能？

你的原实现采用嵌套循环，时间复杂度为O(N*M)（N是_items的长度，M是输入items的长度），当两个数组规模较大时，性能会急剧下降。我们可以通过将目标匹配项存入哈希集合，把查找操作的时间复杂度降到平均O(1)，从而将整体时间复杂度优化到O(N+M)。

优化后的代码实现 #

public class CustomCollection<T> where T : IEquatable<T>
{
    private readonly T[] _items;

    public CustomCollection(T[] items)
    {
        ArgumentNullException.ThrowIfNull(items, nameof(items));
        _items = items;
    }

    public int[] IndexOfAll(T[] items)
    {
        // 校验输入参数
        ArgumentNullException.ThrowIfNull(items, nameof(items));
        
        // 处理输入为空数组的情况，直接返回空结果
        if (items.Length == 0)
        {
            return Array.Empty<int>();
        }

        // 将目标项存入HashSet，实现O(1)平均时间复杂度的查找
        var targetItems = new HashSet<T>(items);
        var result = new List<int>(_items.Length); // 预先分配容量，减少List扩容开销

        for (int i = 0; i < _items.Length; i++)
        {
            if (targetItems.Contains(_items[i]))
            {
                result.Add(i);
            }
        }

        return result.ToArray();
    }
}

优化点说明 #

1. 哈希集合优化查找：使用HashSet<T>存储输入的items，将原本O(M)的遍历查找变成O(1)的哈希查找，大幅降低了大数组场景下的时间开销。
2. 参数校验与边界处理：新增了对items参数的空值校验，以及输入为空数组时的直接返回逻辑，让代码更健壮。
3. 预分配List容量：初始化List<int>时传入_items.Length作为初始容量，避免List在添加元素过程中多次扩容，减少内存分配和拷贝的开销。

注意事项 #

原代码中如果输入的items包含重复元素，会对同一个匹配索引重复添加（比如items = [2,2]且_items[i]=2时，原方法会将i加入结果两次）。优化后的代码因为HashSet会自动去重，每个匹配索引只会被添加一次。如果你的业务需求需要保留原逻辑（重复匹配重复添加），可以改用HashSet之外的方式，比如先统计items中每个元素的出现次数，再遍历_items时按次数添加索引，但这种场景相对少见，通常我们只需要记录每个匹配的索引一次。

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