最接近的三数之和

发表于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，16.3Sum Closet

先看题目描述

这道题与之前做过的三数之和很像，不过那道题是返回所有相加等于 0 的三个数的组合，这个是返回三数相加之和最接近 target 的值

算法和思路

这题的思路和前面的三数之和基本一致，也是排序加上双指针，就是实现细节不一样

算法流程

  • 定义 res 用来维护当前最接近 target 的三数之和，定义 min 用来维护 target 与 res 之差的绝对值

  • 对 nums 数组进行升序排列

  • 遍历 nums 数组

    • 遍历到 nums[i] 时，令 left = i + 1，right = nums.length() - 1
      • 用 sum 记录 nums[i] + nums[left] + nums[right] 的值
      • 若 sum - target 的绝对值小于 min，则更新 res 与 min
      • 若 min = 0，直接返回 res，min > 0 则左移 right 指针，min < 0 则右移 left 指针
      • 重复上述步骤直至 left >= right

  • 返回 res

还有一点要注意的是，当 nums[i] = nums[i - 1] 时，可直接跳过 nums[i]，无需再重复

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            if (i >= 1 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                int minus = sum - target;
                if (Math.abs(minus) < min) {
                    min = Math.abs(minus);
                    res = sum;
                }
                if (minus > 0) right--;
                else if (minus < 0) left++;
                else  return res;
            }
        }
        return res;
    }
}