[解決済み] javaのHashMap.containsValue()の時間的複雑さは何ですか？

質問

で問題を出されました。 O(n) 時間複雑性．

数のリストと数xが与えられたとき、リストの中にxを足す2つの数があるかどうかを調べなさい。

そして、これが私の解答です。

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() メソッドと、時間的複雑さの点で、上記の問題に対してより良い解決策があるかどうか提案してください。ありがとうございました。

どのように解決するのですか？

タイトルの質問に答えるために - 他の人が言及したように。 containsValue なぜなら、キーがなければどこにあるのか分からず、アルゴリズムはマップに格納されているすべての値を調べなければならないからです。

ご質問の本文にある質問（解決方法について）に答えるには、次のような場合かどうかを考えればよいでしょう。 本当に 各数字が何個目になるかをカウントできる一般的な地図が必要です。つまり だけ ある数字が2つ以上現れるかどうかを気にするのは、それがx/2であるときでしょう？それはコーナーケースの匂いがする。そのコーナーケースをチェックするテストを追加すればいいんだ。 if (numberList[i] == requiredSum/2) half++ をセット構築のループの中に入れて、次に if (requiredSum % 2 == 0 && half == 2) return 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;