三数之和问题 | Baeldung中文网

1. Introduction

In this tutorial, we’ll solve the 3SUM problem.

2. Problem Statement

It comes in several variations. We’ll focus on the following one.

There’s an integer array $a=[a_1, a_2, \ldots, a_n]$ and the number . Does the array contain a triple of integers whose sum is $\boldsymbol{s}$ ? Each element can appear in the triple only once.

For example, if a=[1, 0, 3, 17, 7] and s=21 , the solution is a_1=1, a_3=3, a_4=17 but not a_5=7, a_5=7, a_5=7 . As we see, the elements don’t have to be consecutive, and the indices can’t repeat in the solution.

2.1. Importance of 3SUM

3SUM is important in the theory of complexity because many problems from computational geometry, dynamic graphs, and patter matching, are reducible from 3SUM. That means that we can solve 3SUM by solving a constant number of instances of those problems (with some overhead).

That implies that those problems are in a way easier than 3SUM since they appear as its sub-problems. As a result, those problems’ upper bounds hold for 3SUM, and the lower bounds of 3SUM hold for them (provided that the overhead is negligible compared to the problems’ orders of growth).

3. Brute-Force Algorithm

We can find the triple with three nested loops:

algorithm BruteForce3SUM(a, s):
    // INPUT
    //    a =  an integer array [a_1, a_2, ..., a_n]
    //    s = the target sum
    // OUTPUT
    //    A triple a_i, a_j, a_k in a such that a_i + a_j + a_k = s,
    //    or false if no such triplet exists.

    for i <- 1 to n - 2:
        for j <- i + 1 to n - 1:
            for k <- j + 1 to n:
                if a[i] + a[j] + a[k] = s:
                    return a[i], a[j], a[k]

    return false

The idea is to iterate over and check all possible combinations of three elements. We output the triple whose sum is if there is one; otherwise, we return false .

This algorithm is easy to understand and always returns the correct result. However, it’s asymptotically inefficient. In the worst case, no triple sums to , so we run through all the combinations of length 3. Since there are $\binom{n}{3}$ of them, this approach has the O(n^3) time-complexity.

4. The $\boldsymbol{O(n^2)}$ Solution

We can do better. The key idea is to see that a_i + a_j + a_k = s is equivalent to a_k = s - (a_i + a_j) . So, we hash and then calculate the sums of $\binom{n}{2}$ pairs one by one. We iterate over the pairs until we hit the one whose difference from is in the hash map.

If no pair sums to the difference of and another element of , we return false :

algorithm ThreeSumQuadratic(a, s):
    // INPUT
    //    a =  an integer array [a_1, a_2, ..., a_n]
    //    s = the target sum
    // OUTPUT
    //    A triple a_i, a_j, a_k in a such that a_i + a_j + a_k = s,
    //    or false if no such triplet exists.

    map <- an empty hash map

    for i <- 1 to n:
        Insert(a[i], map)

    for i <- 1 to n - 1:
        for j <- i + 1 to n:
            if map contains (s - (a[i] + a[j])):
                return (a[i], a[j], s - (a[i] + a[j]))

    return false

The two nested loops determine the overall complexity. In the worst case, no triple sums to zero, so the algorithm runs all the $\binom{n}{2} = \frac{n(n-1)}{2} \in O(n^2)$ iterations.

5. Conclusion

In this article, we presented two solutions to a variation of the 3Sum problem. The brute-force algorithm is simple but cubic. We can use an asymptotically much faster O(n^2) algorithm if we hash the input array, sum pairs, and look for their negatives in the hash map.

Persistence

REST

Security