当前位置：文江博客话题详情

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

发布于 2024-11-16 08:08:38 字数 104 浏览 6 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

眼波传意 2024-11-23 08:08:38

它不可能是 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);
        }

It can't be NP-Complete as there is an obvious O(n^2) solution with two nested loops over the array and checking if the sum is k.

There is however an O(n) solution using hashtable. Here is the solution in 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);
        }

回复收藏 0 原文

~没有更多了~