[数组]16.3Sum Closest

16.3Sum Closest
题目大意
给定一个数组和一个target，要求找出三个数的和，且这个和最接近target。

双指针法
空间:O(n) 时间:O(n^2)
　#### 闭着眼睛也要记得的解法

（left固定 ＋ left＋right ）－target ＝ diff
如果diff变小，就更新和。
根据和与target的大小差异，移动left／right指针。

JAVA：20ms

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 相似15.3Sums
        Arrays.sort(nums); 
        int temp_diff = Integer.MAX_VALUE;
        int temp_closest = 0;
        
        
        for(int i = 0; i< nums.length -2 ; i++){
            int left = i+1; 
            int right = nums.length -1;
            while(left < right){
                int cur_sum = nums[left] + nums[right] + nums[i];
                int cur_diff =  Math.abs(cur_sum - target);
                //Update
                if(cur_diff < temp_diff ){
                    temp_diff = Math.abs(cur_sum - target);
                    temp_closest = cur_sum;
                }
                //Move left/right pointer
                if(cur_sum < target){
                    left++;
                }else if(cur_sum > target){
                    right--;
                }else{
                    
                    return cur_sum; //cur_sum == target
                }
            }
        }
        return temp_closest;
        
    }
}

.
.
Python : 172ms

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        diff = sys.maxint #记住这个用法
        for i in range(len(nums)-2):
            left = i+1
            right = len(nums)-1
            while(left < right):
                temp_sum = nums[left] + nums[right] + nums[i]
                temp_diff = temp_sum - target
                if (abs(temp_diff) < abs(diff)):
                    diff = temp_diff
                    
                #一个if语句中可以包含多个elif语句，但结尾只能有一个else语句
                if(temp_diff > 0):
                    right -= 1
                elif(temp_diff < 0):
                    left += 1
                else:
                    return temp_sum
        
        return diff + target