寻找abs(A[i]+A[j]-k)最小值的算法：能否优化至O(n)复杂度？

Great question! Let's dig into this problem and whether an O(n) solution exists.

First, let's restate the problem clearly: Given an array of integers (positive and negative), we need to find the minimum value of abs(A[i] + A[j] - k) where i ≠ j. This is equivalent to finding the pair of elements whose sum is closest to k.

Short Answer #

For unconstrained integer arrays (elements can be any positive/negative value with no fixed range), there is no known strict O(n) time complexity solution. The optimal approach remains the sorting + two-pointer method you mentioned, which runs in O(n log n) time.

Why No O(n) Solution for General Cases? #

The core issue here is that this problem is closely tied to the "closest pair sum" problem, which has a lower bound matching that of comparison-based sorting—Ω(n log n). Here's why:

• To find the pair with sum closest to k, you need to compare relative values of elements to each other. Without sorting or some form of ordered structure, you can't efficiently narrow down which pairs might yield the closest sum.
• Hash-based approaches (like those used for the two-sum problem) don't directly translate here. For two-sum, we're looking for an exact match, but here we need the closest match. Checking all possible values near k - A[i] would require knowing the range of elements, which isn't guaranteed for arbitrary arrays.

Exception: Arrays with Bounded Element Ranges #

If your array has elements constrained to a fixed, small range (e.g., all elements are between -M and M where M is a constant much smaller than n), you can achieve an O(n + M) time solution, which approximates O(n) when M << n:

1. Step 1: Create a frequency count array or a hash set to store all elements in O(n) time.
2. Step 2: For each element a in the array, calculate the target value target = k - a. Check the hash set for target, target + 1, and target - 1 (or nearby values within the range) to find the element b (where b ≠ a) that makes abs(a + b - k) as small as possible.
3. Step 3: Track the minimum value found across all elements.

This works because the number of nearby values you need to check is constant (due to the bounded range), making each iteration O(1).

Why the Two-Pointer Method is Still the Best for General Cases #

The sorting + two-pointer approach is optimal for arbitrary arrays:

1. Sorting the array takes O(n log n) time—this is the dominant cost.
2. Using two pointers (starting at the start and end of the sorted array) allows you to traverse the array once in O(n) time, adjusting pointers based on whether the current sum is less than or greater than k to home in on the closest sum.

For example, with the array [-5, 2, 3, 7, -1] and k = 4:

• Sorted array: [-5, -1, 2, 3, 7]
• Start with left pointer at -5, right at 7: sum is 2, abs(2-4) = 2
• Move left pointer to -1: sum is 6, abs(6-4) = 2
• Move left pointer to 2: sum is 9, which is larger than 4, so move right pointer to 3: sum is 5, abs(5-4) = 1 (this is the minimum)

Final Takeaway #

Unless your array has a known, small bounded range, stick with the O(n log n) sorting + two-pointer method—it's the most efficient solution for the general case.

内容的提问来源于stack exchange，提问作者Vedant Dixit