algorithm - サイズ n の入力配列から k に加算されるすべてのペアを出力するプログラムを作成することは可能ですか?

Question

サイズ n の入力配列から k に加算されるすべてのペアを出力するプログラムを作成することは可能ですか? もしそうなら、どのように？この問題は NP-Complete だと聞きました。C/C++ のような典型的なプログラミング言語でこの問題の解決策を提供できるかどうか疑問に思っていました

Answer 1

配列上に 2 つのネストされたループがあり、合計が k であるかどうかをチェックする明らかな O(n^2) ソリューションがあるため、NP-Complete にすることはできません。

ただし、ハッシュテーブルを使用した O(n) ソリューションがあります。C# での解決策は次のとおりです。

        int[] ar = new int[] { 1, 4, 6, 8 };
        int k = 7;

        HashSet<int> set = new HashSet<int>();
        foreach (int n in ar)
        {
            if (set.Contains(n))
                Console.WriteLine("({0}, {1})", k - n, n);

            set.Add(k - n);
        }