Java 中 HashSet.contains 的时间复杂度

Question

在 this video 解释的人说这段代码

boolean sumOfTwo(int[] a,int[] b, int v)
{
    HashSet<Integer> difference=new HashSet();
    for(int i=0;i<a.length;i++)
    {
        int diff=v-a[i];
        difference.add(diff);
    }
    for(int i=0;i<b.length;i++){
        if( difference.contains(b[i]) return true;
    }
    return false;
}

具有线性时间复杂度，但使用 .contains 不会使其成为二次时间吗？因为 .contains 必须检查集合中的每个元素，所以它的时间复杂度为 O(n) 并且它是循环的。

Answer 1

HashSet 中的 contains 在 O(1) 中执行（常数时间）：

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

所以contains不会影响整个算法的复杂度

Java 中 HashSet.contains 的时间复杂度

Time complexity of HashSet.contains in Java

java

hashset