在数组中找到三个元素，其和最接近给定数字

1. Introduction

In this tutorial, we’ll see how to find three elements in an array such that the sum is closest to a given number.

2. Problem Description

Given a number array $\mathbf {A}$ and a target number $\mathbf {t}$ , we want to find three numbers in $\mathbf {A}$ such that their sum is closest to $\mathbf {t}$ . For example, if the array is $\{-1, 2, 1, -4\}$ and our target number is , then the closest sum is 2. Also, the 3 numbers that produce the closest sum are $\{-1, 2, 1\}$ .

3. Brute Force Approach

Let’s uppose the number index of the array starts with , i.e., $A = \{A[0], A[1], ..., A[n-1]\}$ . We can explore all the possible 3 numbers based on their indexes, and keep a track of the difference between $\mathbf {t}$ and the sum of the 3 numbers:

algorithm threeSumClosest(A, n, t):
    // INPUT
    //    A = an integer array with size n
    //    t = the target number
    // OUTPUT
    //    Three numbers in A whose sum is closest to t
    
    minDiff <- infinity
    result <- []
    
    for i <- 0 to n - 3:
        for j <- i + 1 to n - 2:
            for k <- j + 1 to n - 1:
                sum <- A[i] + A[j] + A[k]
                diff <- abs(sum - t)
                if diff < minDiff:
                    minDiff <- diff
                    result <- [A[i], A[j], A[k]]
    
    return result

This algorithm uses three nested loops to go through all possible combinations of 3 numbers in the array . In each iteration, we calculate the difference between the sum of the three numbers and the target number . If the difference is less than the minimum difference we have so far, we’ll record the 3 numbers and update the minimum difference.

Since we have three nested loops over the array , the overall time complexity of this algorithm is O(n^3) , where is the number of elements in the array .

4. Two-pointer Approach

We can solve this problem with the two-pointer approach. Since the two-pointer approach works on a sorted array, we first need to sort the array . To calculate the closest sum of three numbers, we can first fix one number, $\mathbf {A[i]}$ , and then use the two-pointer approach to find the closest sum that contains the fixed number $\mathbf {A[i]}$ :

algorithm threeSumClosest(A, n, t):
    // INPUT
    //    A = an integer array with size n
    //    t = the target number
    // OUTPUT
    //    Three numbers in A whose sum is closest to t
    
    Sort A in ascending order
    minDiff <- infinity
    result <- []
    
    for i <- 0 to n - 3:
        j <- i + 1
        k <- n - 1
        while j < k:
            sum <- A[i] + A[j] + A[k]
            diff <- abs(sum - t)
            if diff < minDiff:
                minDiff <- diff
                result <- [A[i], A[j], A[k]]
    
            if sum < t:
                j <- j + 1
            else:
                k <- k - 1
    
    return result

In this algorithm, we first sort the array in ascending order. Then, we go through each number of to find the closest sum for this number. For a number A[i] , we construct two pointers: j=i+1 and k=n-1 . These two pointers indicate the indexes of the other two numbers, i.e. A[j] and A[k] . Then, we use the two-pointer approach to find the closet sum.

In each iteration of the two-pointer approach, we compare the sum of the three numbers $\{A[i], A[j], A[k]\}$ with our target number . If the sum is less than , we should increase the pointer to make the next sum bigger. Otherwise, we can decrease the pointer to make the next sum smaller. In this way, we can get the sum close to the target number as much as possible.

In the meantime, we also check the difference between the sum and the target number . If the difference is less than the minimum difference we have so far, we’ll record the 3 numbers and update the minimum difference.

In this algorithm, we scan the entire array keeping one element fixed. For each element, we use the two-pointer approach to find the closest sum. The two-pointer approach takes O(n) time for a fixed element. Since we have O(n) possible fixed elements, the overall time complexity is O(n^2) . The sorting takes O(n log n) time. Therefore, the total running time is O(n log n + n^2) which still comes down to O(n^2) .

5. Conclusion

In this tutorial, we showed two algorithms to find three elements such that the sum is closest to a given number. The brute force approach takes O(n^3) time to solve the problem. We can also use a two-pointer approach to solve this problem with a better performance of O(n^2) .

Persistence

REST

Security

1. Introduction

2. Problem Description

3. Brute Force Approach

4. Two-pointer Approach

5. Conclusion