最接近的三数之和

拼搏现实的明天。 2022-12-03 13:20 171阅读 0赞

# 最接近的三数之和 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/3sum-closest/

## 2、题目要求 ##

> **题目描述**

给定一个包括 `n` 个整数的数组 `nums` 和 一个目标值 `target`。找出 `nums` 中的三个整数，使得它们的和与 `target` 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

> **示例：**

输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

## 3、代码思路 ##

排序 + 双指针

1.  最接近的三数之和与三数之和题目的思路相近，都是使用排序 + 双指针
2.  先将数组排序，使用两层循环，可将时间复杂度降为 O(n2)，外层使用 `for` 循环遍历排序之后的数组，内层使用 `while` 循环 + 双指针，搜索最接近目标值的三数之和
3.  假设三数之和用 `curSum` 表示，目标值用 `target` 表示，如果 `curSum == target`，则直接返回 `curSum`；如果 `curSum > target`，表示三数之和大于目标值，`right` 指针左移，尝试减小 `curSum`；如果 `curSum < target`，表示三数之和小于目标值，`left` 指针右移，尝试增大 `curSum`
4.  每次使用当前 `curSum` 和 `target` 的差值，与上次的差值 `lastDiff` 比较，如果这次差值更小，说明三数之和更接近目标值，更新 `curSum` 和 `lastDiff`

## 4、代码实现 ##

代码

/**
     * @ClassName ThreeSumClosestDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/9/3 18:49
     * @Version 1.0
     */
    public class ThreeSumClosestDemo {
        
    
        public static void main(String[] args) {
        
            Solution solution = new Solution();
            int closestSum = solution.threeSumClosest(new int[]{
        1, 1, 1, 0}, 1);
            System.out.println(closestSum);
        }
    
    }
    
    class Solution {
        
        public int threeSumClosest(int[] nums, int target) {
        
            // 对数组进行升序排列
            Arrays.sort(nums);
            // 最接近目标值的三数之和
            int closestSum = 0;
            // 上一次与目标值的差值
            int lastDiff = Integer.MAX_VALUE;
            // 遍历数组，当 i = nums.length - 3时，left = nums.length - 2，right = nums.length - 1，为临界条件
            for (int i = 0; i < nums.length - 2; i++) {
        
                // 上一次的元素和当前相同，跳过此次循环
                if (i > 0 && nums[i] == nums[i - 1]) {
        
                    continue;
                }
                int left = i + 1; // 左指针
                int right = nums.length - 1; // 右指针
                // 当 left < right 时，证明还有元素待验证(枚举)
                while (left < right) {
        
                    // 求三数之和
                    int curSum = nums[i] + nums[left] + nums[right];
                    if (curSum == target) {
        
                        // 如果等于目标值则直接返回
                        return curSum;
                    } else if (curSum > target) {
        
                        // 如果大于目标值，则说明需要尝试减小 curSum，所以 right 指针左移
                        right--;
                    } else {
        
                        // 如果小于目标值，则说明需要尝试增大 curSum，所以 left 指针左移
                        left++;
                    }
                    // 如果这次的差值比上次的差值小，说明这次更接近目标值
                    if (Math.abs(curSum - target) < lastDiff) {
        
                        closestSum = curSum;
                        lastDiff = Math.abs(curSum - target);
                    }
                }
            }
            return closestSum;
        }
    }