LeetCode之3Sum Closest（Kotlin）

问题：
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

方法：
最原始的方法是三层循环遍历，求所有三个数的sum，然后找出最接近target的sum，但是这样的算法复杂度比较高，需要O(n^{3)的时间复杂度，通过排序可以降低比较的次数，先对数组进行排序，因为数组有序，如果sum大于target就从后面移动index，如果sum小于target就从前面移动index，向中间逼近，这样就可以减少比较的次数，这样的算法时间复杂度是O(n}2)

具体实现：

class ThreeSumClosest {
    // -4, -1, 2, 1,
    // 双逼近算法
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var sum = nums[0] + nums[1] + nums[2]
        nums.sort()
        for (x in nums.indices) {
            var i = x + 1
            var j = nums.lastIndex
            while (i < j) {
                val curSum = nums[i] + nums[j] + nums[x]
                val curDiff = abs(sum - target)
                val diff  = abs(curSum - target)
                if (diff < curDiff) {
                    sum = curSum
                }
                if (curSum - target > 0) {
                    j--
                } else if(curSum - target < 0) {
                    i++
                } else {
                    return sum
                }
            }
        }
        return sum
    }
}

fun main(args: Array<String>) {
    val nums = intArrayOf(0,2,1,-3)
    val target = 1
    val threeSumClosest = ThreeSumClosest()
    println(threeSumClosest.threeSumClosest(nums, target))
}

有问题随时沟通

具体代码实现可以参考Github