【Lintcode】1478. Closest Target Value

题目地址：

https://www.lintcode.com/problem/closest-target-value/description

给定一个数组，再给定一个数 $x$，求数组中的两个数的和中最大的小于 $x$的那个和。思路是先排序，然后用两个指针从两头走。代码如下：

import java.util.Arrays;public class Solution {/*** @param target: the target* @param array: an array* @return: the closest value*/public int closestTargetValue(int target, int[] array) {// Write your code hereif (array == null || array.length < 2) {return -1;}Arrays.sort(array);int i = 0, j = array.length - 1;int res = Integer.MIN_VALUE;while (i < j) {int sum = array[i] + array[j];if (sum > target) {j--;} else if (sum < target) {res = Math.max(res, sum);i++;} else {return sum;}}return res == Integer.MIN_VALUE ? -1 : res;}
}

时间复杂度 $O(n\log n)$，空间 $O(1)$。