抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

Leetcode 16. 最接近的三数之和

16. 最接近的三数之和

乍一看,真像这道题:16 | 面试题:三数之和

解法:排序 + 双指针

思路:我本来按三数之和思路进行调整,想了想,直接看了下官方的处理,看代码就能理解,于是,直接选择最优解了。(自己想,忽略了双指针移动过程中的去重

class Some16Solution {

    fun threeSumClosest(nums: IntArray, target: Int): Int {
        val n = nums.size
        Arrays.sort(nums)
        //这里 不要用 Int.MaxValue
        var ans = 100000

        for (first in 0 until n) {
            //过滤和上次不同
            if (first > 0 && nums[first] == nums[first - 1]) continue
            //从右开始
            var left = first + 1
            var right = n - 1
            while (left < right) {

                val sum = nums[first] + nums[left] + nums[right]
                if (sum == target) return sum

                if (Math.abs(sum - target) < Math.abs(ans - target)) ans = sum
                if (sum > target) {
                    //大于 移动右边的指针
                    var temp = right - 1
                    while (left < temp && nums[right] == nums[temp]) temp--
                    right = temp
                } else {
                    //小于 移动左边的指针
                    var temp = left + 1
                    while (temp < right && nums[left] == nums[temp]) temp++
                    left = temp
                }
            }
        }
        return ans
    }
}

这里的双指针有道更简单的题:11. 盛最多水的容器

简陋文章:Leetcode 11. 盛最多水的容器


0条评论

发表评论