O(NlogN) finding 3 numbers that have a sum of any arbitrary T in an array

Question

Given an array A of integers, find any 3 of them that sum to any given T.

I saw this on some online post, which claims it has a O(NlogN) solution.

For 2 numbers, I know hashtable could help for O(N), but for 3 numbers, I cannot find one.

I also feel this problem sounds familar to some hard problems, but cannot recall the name and therefore cannot google for it. (While the worst is obviously O(N^3), and with the solution to 2 numbers it is really O(N^2) )

It does not really solve anything in the real world, just bugs me..

Any idea?

Many other similar posts on the right. http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number — , Dec 07 '09 at 17:36
This is similar to Subset Sum Problem, which is NP-Complete. But limiting the subset length to 3, it might be possible to find a fast solution. — Erkan Haspulat, Dec 07 '09 at 17:39
One hard (NP complete) problem that has similarities to this one is called the http://en.wikipedia.org/wiki/Knapsack_problem . Of course the constraint here that you pick only 3 integers make it at worst O(n^3), so it's not exactly the same. — Pascal Cuoq, Dec 07 '09 at 17:39
[Finding three elements in an array whose sum is closest to a given number](https://stackoverflow.com/q/2070359) presents some O(n^2) solutions to this problem. — Bernhard Barker, Nov 05 '17 at 17:48

score 14 · Accepted Answer · answered Dec 07 '09 at 17:38

14

I think your problem is equivalent to the 3SUM problem.

answered Dec 07 '09 at 17:38

Nick Dandoulakis

42,588
16
104
136

score 3 · Answer 2 · answered Jun 15 '13 at 06:51

3

For three sum problem, you cannot find a solution better than O(n^2). You can refer to http://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

answered Jun 15 '13 at 06:51

Wenjing

96
1
4

Not sure what used to be on that page, but it's not relevant now. And that's why you quote things. – Zachary Vance Apr 25 '15 at 06:38

score 2 · Answer 3 · edited Oct 05 '12 at 19:12

2

2SUM problem can be solved in O(nlgn) time.

First sort the array which takes at most O(nlgn) operations. Now at ith iteration we picked the element a[i] and find the the element -a[i] in the remaining part of the array (i.e from i+1 to n-1) and this search could be conducted in binary search which takes at most lgn time. So overall it will take O(nlgn) operations.

But 3SUM problem cant be solved in O(nlgn) time . We could reduce it to O(n^2)

edited Oct 05 '12 at 19:12

Steve Czetty

6,147
9
39
48

answered Aug 15 '12 at 17:02

Avijit Dutta

31
1

6

For two some problem, it could be reduced to O(N) if we use hash table. – Avinash Feb 26 '16 at 09:23

score 0 · Answer 4 · answered Dec 07 '09 at 17:36

0

Sounds like a homework question...

If you can find two values that sum to N but you want to extend the search to three values, couldn't you, for each value M in the set, look for two values that sum to (N - M)? If you can find two values that sum to a specific value in O(log N) time, then that will be O(N log N).

answered Dec 07 '09 at 17:36

Tim Sylvester

22,897
2
80
94

How are you going to find two numbers that sum to a specific value in log(N) time? – Peter Recore Dec 07 '09 at 17:43
Good question, I don't know. I didn't say it was possible, only that you would need to be able to do it in order solve the problem in the particular way that I described. – Tim Sylvester Dec 07 '09 at 17:54

score 0 · Answer 5 · edited Jun 20 '20 at 09:12

0

I think this is just the subset sum problem

If so, it is NP-Complete.

EDIT: Never mind, it is 3sum, as stated in another answer.

edited Jun 20 '20 at 09:12

Community

1
1

answered Dec 07 '09 at 17:39

Peter Recore

14,037
4
42
62

1

There are less than n^3 ways to pick 3 numbers among n, so it can hardly be NP-complete. The trivial brute-force algorithm is O(n^3). – Pascal Cuoq Dec 07 '09 at 17:41
yup. the subset problem is NP, but this is not the subset problem. the subset problem doesn't specify how many numbers will be added together, while this problem restricts it to exactly 3. – Peter Recore Dec 07 '09 at 18:46

score 0 · Answer 6 · answered Jan 22 '23 at 00:27

0

Yes! 3SUM has an O(nlogn) algorithms using Fast Fourier Transform(FFT), here is a general idea:

answered Jan 22 '23 at 00:27

JIAYUAN HONG

33
5

score -3 · Answer 7 · edited May 06 '16 at 19:49

Lifted directly from https://en.wikipedia.org/wiki/3SUM

    sort(S);

    for i=0 to n-3 do

        a = S[i];
        start = i+1;

        end = n-1;

        while (start < end) do

           b = S[start];
           c = S[end];
           if (a+b+c == 0) then
              output a, b, c;
              // Continue search for all triplet combinations summing to zero.
               start = start + 1
               end = end - 1

           else if (a+b+c > 0) then
              end = end - 1;
           else
              start = start + 1;
           end
        end
     end

O(NlogN) finding 3 numbers that have a sum of any arbitrary T in an array

7 Answers7

Linked

Related