题意
从给定的数组中选出三个数,使得三个数的和最接近目标值。
思路
- 想法1:暴力,(O(n^3))。
- 想法2:排序 双指针。上题中的想法可直接拿过来用,改一下返回的结果就可以了。时间复杂度:(O(n^2)),空间复杂度:(O(n))。
代码
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
sort(nums.begin(), nums.end());
int L, R;
int res = nums[0] nums[1] nums[2];
for(int i = 0; i < len; i)
{
L = i 1;
R = len - 1;
while(L < R)
{
int sum = nums[i] nums[L] nums[R];
if(sum == target) return target;
if(abs(sum - target) < abs(res - target)) res = sum;
if(sum > target)
--R;
else
L;
}
}
return res;
}
};
总结
排序 指针。