algorithm - 是否可以编写一个程序来打印从大小为 n 的输入数组中添加到 k 的所有对

Question

是否可以编写一个程序来打印从大小为 n 的输入数组中添加到 k 的所有对。如果有怎么办？我听说这个问题是NP-Complete。我想知道我们是否可以用典型的编程语言（如 C/C++）来解决这个问题

Answer 1

它不能是 NP 完全的，因为有一个明显的 O(n^2) 解决方案，在数组上具有两个嵌套循环并检查总和是否为 k。

然而，有一个使用哈希表的 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);
        }