LeetCode 16 最接近的三数之和（难度：Medium）

叁歲伎倆 2022-02-01 12:07 170阅读 0赞

**题目大意：找nums数组中的三个数，使它们的和最接近目标值target，并且只有一组解。**

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

解法：

package pers.leetcode;
    
    import java.util.Arrays;
    
    /**
     * 3Sum Closest
     * 难易程度: Medium
     *
     * @author admin
     * @date 2019/5/11 9:18
     */
    public class LeetCode16 {
    
        public static void main(String[] args) {
            int[] arrays = {1, 1, -1, -1, 3};
            int result = threeSumClosest(arrays, -1);
            System.out.println("LeetCode16 答案: " + result);
        }
    
        public static int threeSumClosest(int[] nums, int target){
            Arrays.sort(nums);
            int result = 10086;
            int d_value = 10086;
    
            for (int i = 0; i < nums.length - 2; i++){
                // 去重
                if (i >= 1 && nums[i] == nums[i-1]){
                    continue;
                }
    
                int j = i + 1;
                int k = nums.length - 1;
    
                while (j < k){
                    int sum;
                    sum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(sum - target) < d_value){
                        d_value = Math.abs(sum - target);
                        result = sum;
                    }
                    if (sum > target){
                        // 减小当前三数总和，尽量接近目标值
                        k--;
                    }else {
                        // 增大当前三数之和，尽量接近目标值
                        j++;
                    }
                }
            }
            return result;
        }
    }