开发者

Is it possible to write a program to print all pairs that add to k from an input array of size n [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

Is it possible to write a program to print all pairs that add to k开发者_JAVA技巧 from an input array of size n. If so how? I heard this problem is NP-Complete. I was wondering if we can provide a solution to this problem in typical programming languages like C/C++


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

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜