LintCode 533 Two Sum - Closest to target

思路

双指针算法。首先将数组排序，然后设置一头一尾两个指针left和right,diff差值需要初始化为Integer.MAX_VALUE。计算temp=target-(nums[left]+nums[right])，并更新diff=min{diff,abs(temp)}若大于0则说明二者之和小了，那么left需要右移才能变大；若小于0则说明二者之和大了，right需要左移才能变小；若为0那么找到目标，直接返回0.

代码

public int twoSumClosest(int[] nums, int target) {
    // write your code hereint left = 0, right = nums.length-1;int diff = Integer.MAX_VALUE;Arrays.sort(nums);while(left < right){
    int temp = target-(nums[left]+nums[right]);diff = Math.min(diff, Math.abs(temp));if(temp > 0){
    left++;}else if(temp < 0){
    right--;}else{
    return 0;}}return diff;}

复杂度分析

时间复杂度O(nlogn), 空间复杂度O(1)