eetcode - 3sum closest(kotlin)


level - medium
[質問]
配列の中の3つの数字の加算する値とtargetの最も近い値を求めます
[example 1]
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
[解決策]
まず二つの方法でこの問題を解いた.
これから説明するのは、最初に思いついた解決策です.
3つの和を選ぶからだ.
組み合わせで3つを選ぶことにした.
ここで組合せですべての3つのケースの数を求めるとする.
タイムアウトが発生する可能性があります.アレイをソートしてください.
その配列から3つ抽出し,この3つとtargetの差が0であれば
探すのではなく、出る方法で行います.
import kotlin.math.abs

class Solution {
    var min = Int.MAX_VALUE
    var sumOfThree = 0
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        nums.sort()
        combination(nums, IntArray(3), 3, 0, 0, target)
        return sumOfThree
    }

    fun combination(arr: IntArray, result: IntArray, r: Int, current: Int, start: Int, target: Int) {
        if(r == current) {
            var sum = 0
            for(r in result) {
                sum += r
            }

            val difference = abs(sum - target)
            if(difference < min) {
                min = difference
                sumOfThree = sum
            }

            return
        }
        
        if(min == 0) {
            return
        }

        for(i in start until arr.size) {
            result[current] = arr[i]
            combination(arr, result, r, current+1, i+1, target)
        }
    }
}
このように行うと、確認には272 msが必要です.

直感は私に、提出後、その時間分布図を見てこのように解いたのではないと教えてくれた.
解決策を見て、また解いてみました.
two-pointerで問題を解決します.
上から下へ順にブラウズ
これは3つの和を求めて、最小の差を求める方法です.
import kotlin.math.abs

class Solution {
    fun threeSumClosest(nums: IntArray, target: Int): Int {
        var difference = Int.MAX_VALUE
        nums.sort()

        for(i in nums.indices) {
            if(difference == 0) {
                break
            }

            var low = i+1
            var high = nums.size-1
            while(low < high) {
                val sum = nums[i] + nums[low] + nums[high]
                if(abs(target-sum) < abs(difference)) {
                    difference = target - sum
                }

                // 배열이 정렬되어 있는것을 잊지말자
                if(sum < target) {	// 합이 target보다 작으니까 아래에서 위로 올라가기
                    ++low
                } else {	// 합이 target보다 크니까 위에서 아래로 내려가기
                    --high
                }
            }
        }

        return target-difference
    }
}
前述したように,再解離後に提出する場合,192 msであることが確認できる.

二重ポインタ方式を脳に記録します...