16.3Sum Closest
题目大意
给定一个数组和一个target，要求找出三个数的和，且这个和最接近target。
双指针法
空间:O(n) 时间:O(n^2)
#### 闭着眼睛也要记得的解法
（left固定 ＋ left＋right ）－target ＝ diff
如果diff变小，就更新和。
根据和与target的大小差异，移动left／right指针。
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
