【leetcode刷题】T4-3Sum Closest
今天分享leetcode第4篇文章，也是leetcode第16题—3Sum Closest，地址是：https://leetcode.com/problems/3sum-closest/
【英文题目】
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).【中文题目】
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).【思路】
这道题和3Sum以及Two Sum II类似，比较直观的有一种解法：暴力破解，得到所有的三数之和，返回距离target最近的值，时间复杂度O(n^3)
那么时间复杂度能降低吗？是否可以参考Two Sum II呢？
当然可以。
a+b+c 靠近 target，也就是b+c 靠近 target-a，（数组有序的情况下）我们可以使用Two Sum II的方法（两个指针“多退少补”）只用O(n)的时间便得到最靠近 target-a的b+c值。这样，总的时间复杂度是O(n^2)
【代码】
python版本
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
length = len(nums)
# target2用于存储当前最接近的值，min_dis存储其与target的距离
target2 = 0
min_dis = sys.maxsize
for i in range(length-2):
# 相同元素，不再考虑
if i > 0 and nums[i] == nums[i-1]:
continue
# 转换为2sum
tmp_target = target - nums[i]
l, r = i+1, length-1
while l < r:
tmp_sum = nums[l] + nums[r]
# 等于tmp_target，不可能有距离更近的，直接返回结果
if tmp_sum == tmp_target:
return target
# 改变下标前，首先判断是否更加接近
if abs(tmp_target - tmp_sum) < min_dis:
min_dis = abs(tmp_target - tmp_sum)
target2 = tmp_sum + nums[i]
if tmp_sum > tmp_target:
r -= 1
else:
l += 1
return target2C++版本
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
//排序
sort(nums.begin(), nums.end());
// target2用于存储当前最接近的值，min_dis存储其与target的距离
int target2 = 0;
int min_dis = INT_MAX;
bool flag = true;
for(int i=0; flag && i < nums.size()-2; i++){
if(i > 0 && nums[i] == nums[i-1])
continue;
int tmp_target = target - nums[i];
int l=i+1, r=nums.size()-1;
while(l < r){
int tmp_sum = nums[l] + nums[r];
// 等于tmp_target，不可能有距离更近的，直接返回结果
if(tmp_sum == tmp_target){
target2 = target;
flag = false;
break;
}
// 改变下标前，首先判断是否更加接近
if(abs(tmp_target - tmp_sum) < min_dis){
min_dis = abs(tmp_target - tmp_sum);
target2 = tmp_sum + nums[i];
}
if(tmp_sum > tmp_target)
r--;
else
l++;
}
}
return target2;
}
};需要注意的是，leetcode使用的c++编译器必须是在函数最后返回结果，因此需要使用break跳出while循环。但是，while循环外还有一层循环，可以通过设置标记flag来跳出for循环。
【总结】
对于数组求和问题，一般有三种方法：首先是暴力破解，第二是使用hash表，第三是有序数组左右指针“多退少补”