今天分享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 target2
C++版本
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表,第三是有序数组左右指针“多退少补”