3Sum Closest(最接近的三数之和) – 每天一道算法题

题目 #

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).

题目大意 #

给定一个数组,要求在这个数组中找出 3 个数之和离 target 最近。

解题思路 #

这一题看似和第 15 题和第 18 题很像,都是求 3 或者 4 个数之和的问题,但是这一题的做法和 15,18 题完全不同。

这一题的解法是用两个指针夹逼的方法。先对数组进行排序,i 从头开始往后面扫。这里同样需要注意数组中存在多个重复数字的问题。具体处理方法很多,可以用 map 计数去重。这里笔者简单的处理,i 在循环的时候和前一个数进行比较,如果相等,i 继续往后移,直到移到下一个和前一个数字不同的位置。j,k 两个指针开始一前一后夹逼。j 为 i 的下一个数字,k 为数组最后一个数字,由于经过排序,所以 k 的数字最大。j 往后移动,k 往前移动,逐渐夹逼出最接近 target 的值。

这道题还可以用暴力解法,三层循环找到距离 target 最近的组合。具体见代码。

java代码 #

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        // 枚举 a
        for (int i = 0; i < n; ++i) {
            // 保证和上一次枚举的元素不相等
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 使用双指针枚举 b 和 c
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果和为 target 直接返回答案
                if (sum == target) {
                    return target;
                }
                // 根据差值的绝对值来更新答案
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    // 如果和大于 target,移动 c 对应的指针
                    int k0 = k - 1;
                    // 移动到下一个不相等的元素
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    // 如果和小于 target,移动 b 对应的指针
                    int j0 = j + 1;
                    // 移动到下一个不相等的元素
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
}

golang代码 #

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    var (
        n = len(nums)
        best = math.MaxInt32
    )

    // 根据差值的绝对值来更新答案
    update := func(cur int) {
        if abs(cur - target) < abs(best - target) {
            best = cur
        }
    }

    // 枚举 a
    for i := 0; i < n; i++ {
        // 保证和上一次枚举的元素不相等
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        // 使用双指针枚举 b 和 c
        j, k := i + 1, n - 1
        for j < k {
            sum := nums[i] + nums[j] + nums[k]
            // 如果和为 target 直接返回答案
            if sum == target {
                return target
            }
            update(sum)
            if sum > target {
                // 如果和大于 target,移动 c 对应的指针
                k0 := k - 1
                // 移动到下一个不相等的元素
                for j < k0 && nums[k0] == nums[k] {
                    k0--
                } 
                k = k0
            } else {
                // 如果和小于 target,移动 b 对应的指针
                j0 := j + 1
                // 移动到下一个不相等的元素
                for j0 < k && nums[j0] == nums[j] {
                    j0++
                }
                j = j0
            }
        }
    }
    return best
}

func abs(x int) int {
    if x < 0 {
        return -1 * x
    }
    return x
}

python代码 #

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = 10**7
        
        # 根据差值的绝对值来更新答案
        def update(cur):
            nonlocal best
            if abs(cur - target) < abs(best - target):
                best = cur
        
        # 枚举 a
        for i in range(n):
            # 保证和上一次枚举的元素不相等
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 使用双指针枚举 b 和 c
            j, k = i + 1, n - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                # 如果和为 target 直接返回答案
                if s == target:
                    return target
                update(s)
                if s > target:
                    # 如果和大于 target,移动 c 对应的指针
                    k0 = k - 1
                    # 移动到下一个不相等的元素
                    while j < k0 and nums[k0] == nums[k]:
                        k0 -= 1
                    k = k0
                else:
                    # 如果和小于 target,移动 b 对应的指针
                    j0 = j + 1
                    # 移动到下一个不相等的元素
                    while j0 < k and nums[j0] == nums[j]:
                        j0 += 1
                    j = j0

        return best

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注