【LeeCode】16. 最接近的三数之和

【题目描述】

给你一个长度为 ​​n​​​ 的整数数组 ​​nums​​ 和 一个目标值 ​​target​​​。请你从 ​​nums​​ 中选出三个整数，使它们的和与 ​​target​​ 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

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

【示例】

【代码】​​画手大鹏​​

package com.company;

import java.util.Arrays;

// 2022-02-07
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 如果对顺序没要求的题目, 数组一定要排序
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++){
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end){
                int sum = nums[start] + nums[end] + nums[i];
                if (Math.abs(target - sum) < Math.abs(target - ans)){
                    ans = sum;
                }
                if (sum > target){
                    end--;
                }else if (sum < target){
                    start++;
                }else{
                    return ans;
                }
            }
        }
        return ans;
    }
}


public class Test {
    public static void main(String[] args) {
        new Solution().threeSumClosest(new int[]{-1,2,1,-4}, 1);  // 输出：2
        new Solution().threeSumClosest(new int[]{0,0,0}, 1);  // 输出： 0
        new Solution().threeSumClosest(new int[]{0, 1, 2}, 0);  // 输出：3
        new Solution().threeSumClosest(new int[]{1,1,1,1}, 0);  // 输出: 3
        new Solution().threeSumClosest(new int[]{1,1,1,0}, -100);  // 输出: 2
    }
}

【代码】admin

通过率 18/98, 错在了是按顺序查找的，其实题目里说的是找3个数,即任意3个数字

package com.company;

import java.util.Arrays;

// 2022-02-07
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length == 3){
            System.out.println(Arrays.stream(nums).sum());
            return Arrays.stream(nums).sum();
        }
        int sum1 = nums[0] + nums[1] + nums[2];
        int sum = 0;
        for (int i = 1; i + 2 < nums.length; i++){
            sum = 0;
            int j = i;
            while ( j <= i + 2) {
                sum += nums[j];
                j++;
            }
            if (Math.abs(target - sum) < Math.abs(target - sum1)){
                sum1 = sum;
            }
        }
        System.out.println(sum1);
        return sum1;
    }
}


public class Test {
    public static void main(String[] args) {
        new Solution().threeSumClosest(new int[]{-1,2,1,-4}, 1);  // 输出：2
        new Solution().threeSumClosest(new int[]{0,0,0}, 1);  // 输出： 0
        new Solution().threeSumClosest(new int[]{0, 1, 2}, 0);  // 输出：3
        new Solution().threeSumClosest(new int[]{1,1,1,1}, 0);  // 输出: 3
        new Solution().threeSumClosest(new int[]{1,1,1,0}, -100);  // 输出: 2
    }
}