java - java中HashMap.containsValue()的时间复杂度是多少？

Question

我得到了一个O(n)时间复杂度的问题:

“给定一个数字列表和数字 x。查找列表中是否有 2 个数字加起来为 x？”

这是我的解决方案:

public class SumMatchResult {

  public static void main(String[] args){
    int[] numberList = {6,1,8,7,4,6};
    int requiredSum = 8;
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum);
    if(isSumPresent) {
      System.out.println("Numbers exist");
    }else {
      System.out.println("Numbers donot exist");
    }
  }

  private static boolean checkSumPresentHash(int[] numberList, int requiredSum) {
    Map<Integer, Integer> m = new HashMap<Integer,Integer>();
    int count = 0;
    for(int i=0;i<numberList.length;i++){
      m.put(i, numberList[i]);
    }
    for(int i=0;i<numberList.length;i++){
      if(m.containsValue(requiredSum - numberList[i])){
        count++;
      }
    }
    if(count>1){
        return true;
    }
    return false;
  }

}

我正在使用 HashMap.containsValue() 而不是使用 HashSet.contains() 肯定具有 O(1) 的复杂性> 因为，我必须考虑我的输入可能包含相同值的情况。例如，在上述情况下，我可以有一组输入值 {3,6,4,4,7} 与 sum 8 匹配，这应该返回 true。

我上面的解决方案的时间复杂度取决于 HashMap.containsValue() 方法的复杂度。请阐明 containsValue() 方法的时间复杂度，并建议我在时间复杂度方面是否有上述问题的更好解决方案。谢谢。

Answer 1

要回答标题中的问题-正如其他人所说，containsValue是O(n)，因为没有 key 它不知道它在哪里并且算法必须遍历所有 map 中存储的值。

要回答问题正文中的问题 - 关于如何解决问题 - 只需考虑您是否真的需要一张通用 map ，该 map 可以计算您看到每个数字的实例数。我的意思是，唯一你会关心一个数字是否不止一次出现的时候是它的 x/2，对吧？这对我来说就像一个角落里的箱子。只需添加一个检查该极端情况的测试 - 比如在你的集合构造循环中嵌入 if (numberList[i] == requiredSum/2) half++ ，然后 if (requiredSum % 2 == 0 && half == 2) 在它之后返回 true(参见下面的其他变体)。

然后你可以只遍历集合并为每个项目检查 requiredSum-item 是否也出现在集合中。

总结(尽可能提前退出):

Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
    if (num == requiredSum/2 && requiredSum % 2 == 0) {
        if (halfSeen) return true;
        halfSeen = true;
    } else {
        seen.add(num);
    }
}
for (int num : seen) {
    if (seen.contains(requiredSum - num)) return true;
}
return false;