首页 > itarticle > 16.3sum closet

16.3sum closet

admin 12月 10, 2020 0

问题

https://leetcode.com/problems/3sum-closest/description/
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:

1 2	Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路

先升序排序，从头和尾往中靠拢，如果三数之和大于target，则右边缩进一位，否则左边扩大一位，边遍历的同时检查是否有更合适的数并记录。

代码

public int (int[] num, int target) {
    int result = num[0] + num[1] + num[num.length - 1];
    Arrays.sort(num);
    for (int i = 0; i < num.length - 2; i++) {
        int start = i + 1, end = num.length - 1;
        while (start < end) {
            int sum = num[i] + num[start] + num[end];
            if (sum > target) {
                end--;
            } else {
                start++;
            }
            if (Math.abs(sum - target) < Math.abs(result - target)) {
                result = sum;
            }
        }
    }
    return result;
}