16.3sum-closest.md

16. 3Sum Closest

The idea is similar to 15. 3Sum:

• If we find the exact sum, return it.
• Otherwise, we try to find the closest sum to target.

fun threeSumClosest(nums: IntArray, target: Int): Int {
    nums.sort()
    var resultSum = Int.MAX_VALUE
    var minDiff = Int.MAX_VALUE
    for (i in 0 until nums.size) {
        val first = nums[i]
        
        var j = i + 1
        var k = nums.size - 1
        while (j < k) {
            val sum = first + nums[j] + nums[k]

            // If we find the exact sum, return it.
            if (sum == target) return sum

            // Try to find the closest sum to `target`.
            val diff = abs(sum - target)
            if (diff < minDiff) {
                minDiff = diff
                resultSum = sum
            }

            if (sum > target) {
                k--
            } else if (sum < target) {
                j++
            }
        }
    }
    return resultSum
}

• Time Complexity: O(n^2).
• Space Complexity: O(lg n) for sorting.