Leetcode 16 最接近的三数之和 ( 3Sum Closest *Medium* ) 题解分析

发表于 分类于 ， 阅读次数： 阅读次数： Disqus：

题目介绍

Given an integer array nums of length n 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 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).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4

简单解析

这个题思路上来讲不难，也是用原来三数之和的方式去做，利用”双指针法”或者其它描述法，但是需要简化逻辑

code

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
27
28
29
30
31
32
33
34
35
36
public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        // 当前最近的和
        int closestSum = nums[0] + nums[1] + nums[nums.length - 1];
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || nums[i] != nums[i - 1]) {
                // 左指针
                int left = i + 1;
                // 右指针
                int right = nums.length - 1;
                // 判断是否遍历完了
                while (left < right) {
                    // 当前的和
                    int sum = nums[i] + nums[left] + nums[right];
                    // 小优化，相等就略过了
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 这里判断，其实也还是希望趋近目标值
                    if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                    // 判断是否需要替换
                    if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                        closestSum = sum;
                    }
                }
            }
        }
        return closestSum;
    }

结果