LeetCode 16：3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

传入一个数组和一个目标值，找出数组里的三个数，使得它们的和最靠近目标值，返回和

看上去很简单，先暴力O(n^3)来一发

Java源码

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closest = Integer.MAX_VALUE;
        int sum = 0;
        int len = nums.length;
        
        for (int i = 0; i < len - 2; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                for (int k = j + 1; k < len; k++) {
                    int temp = nums[i] + nums[j] + nums[k] - target;
                    if (temp < 0) {
                        temp = -temp;
                    }
                    if (temp < closest) {
                        closest = temp;
                        sum = nums[i] + nums[j] + nums[k];
                    }
                    
                }
            }
        }
        
        return sum;
    }
}

出乎意料的是，居然没有超时

用left，right指针逼近再来一次，首先排序，然后对于nums[i]，右边更大的部分，一个left指针，一个right指针，如果和小于target，left右移，如果大于target，right左移，最后求一个最小值，返回和即可

package com.maoxiaomeng;

import java.util.Arrays;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int minSum = 0;
        int closest = Integer.MAX_VALUE;

        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 2; i++) {
            int left = i + 1;
            int right = len - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                //-1, 1, 2, -4}
                //i left    right
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    return target;
                }
                int temp = sum - target;
                if (temp < 0) {
                    temp = -temp;
                }
                if (closest > temp) {
                    closest = temp;
                    minSum = sum;
                }
                
            }
        }
        
        return minSum;
    }
}

比较简单