Three Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers.

Source

package questions

import algorithmdesignmanualbook.print
import kotlin.math.abs
import kotlin.test.assertEquals

/**
 * Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
 * Return the sum of the three integers.
 *
 * [Source](https://leetcode.com/problems/3sum-closest/)
 */
fun threeSumClosest(nums: IntArray, target: Int): Int {
    require(nums.size >= 3)
    val sorted = nums.sorted()
    var closest = sorted[0] + sorted[1] + sorted.last()

    for (i in 0..sorted.lastIndex) {
        // `i` is fixed, left & right keeps converging to middle
        var left = i + 1
        var right = sorted.lastIndex
        while (left < right) {
            // sum right now
            val sums = sorted[left] + sorted[right] + sorted[i]
            if (sums == target) {
                // closest value is 0 so return immediately
                println("${sorted[left]} ${sorted[right]} ${sorted[i]}")
                return sums
            } else if (abs(sums - target) < abs(closest - target)) {
                // update if closer value is found
                println("${sorted[left]} ${sorted[right]} ${sorted[i]}")
                closest = sums
            }
            if (sums > target) {
                // Sum is larger so decrease right index
                right -= 1
            } else if (sums < target) {
                // Smaller so increase left index
                left += 1
            }
        }
    }
    return closest
}


fun main() {
    assertEquals(expected = 2, threeSumClosest(intArrayOf(-4, -1, 1, 2), 1).print())
    assertEquals(expected = 5, threeSumClosest(intArrayOf(-1, 0, 1, 2, 3, 4, 6), 5).print())
    assertEquals(expected = 5, threeSumClosest(intArrayOf(-1, 0, 1, 2, 3, 4, 7), 5).print())
    assertEquals(expected = 6, threeSumClosest(intArrayOf(-1, 0, 1, 2, 10, 7), 5).print())
}

---

View on GitHub

Updated on 2021-10-11