leetcode16-3Sum Closest

题目

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

分析

这道题目和那道3Num的题目很类似，解题思路也是类似的，我们先对数组排序，然后固定一个元素，通过双指针遍历剩下的元素，用一个哨兵记录三个元素的和与target的diff，分别处理三个元素的和小于target，大于target，等于target这三种情况即可

import java.util.Arrays;

public class threeSumClosest {
	public static void main(String[] args) {
		int[] arr = {-1,2,1,-4};
		System.out.println(getClosest(arr,1));
	}
	public static int getClosest(int[] nums,int target) {
		int len = nums.length;
		Arrays.sort(nums);
		int ret = Integer.MAX_VALUE;
		int res = 0;
		for(int i = 0;i<len-2;i++) {
			if(i > 0 && nums[i] == nums[i-1]) {
				continue;
			}
			int j = i+1;
			int k = len-1;
			while(j<k) {
				int sum  = nums[i] + nums[j] + nums[k];
				if(target < sum) {
					int diff = sum - target;
					if(diff < ret) {
						ret = diff;
						res = sum;
					}
					j++;
				} else if(target > sum) {
					int diff = target - sum;
					if(diff < ret) {
						ret = diff;
						res = sum;
					}
					k--;
				} else {
					return sum;
				}
			}
		}
		return res;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42