文章目录

原题

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).

思路

本题目的解题思路和3Sum很像,区别在于3Sum求解的是三个数字和为target(即为0),然而3SumClosest无非就是求解三个数字和与target最近的一个状态。
很容易地可以想到,将每次求解的距离,即三个数字和与target的差值记录下来,并每次求解时进行比较,寻求最小的距离。

代码

[code lang=”cpp”]
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
vector<int> rs;
int l = nums.size(), dist = 100000000;
sort(nums.begin(), nums.end());

for (int i = 0; i < l – 2; ++i) {
int f = i + 1, b = l – 1;
if (i – 1 >= 0 && nums[i] == nums[i – 1]) continue;
while (f < b) {
if (nums[f] + nums[b] + nums[i] – target > 0) {
if (abs(dist) > abs(nums[f] + nums[b] + nums[i] – target)) {
dist = nums[f] + nums[b] + nums[i] – target;
}
while(nums[b] == nums[–b]) {}
} else if (nums[f] + nums[b] + nums[i] – target < 0) { if (abs(dist) > abs(nums[f] + nums[b] + nums[i] – target)) {
dist = nums[f] + nums[b] + nums[i] – target;
}
while(nums[f] == nums[++f]) {}
} else {
return target;
}
}
}

return dist + target;
}
};
[/code]

时间复杂度:O(n^2)
空间复杂度:O(n)


原题:https://leetcode.com/problems/3sum-closest/description/
文章来源:胡小旭 => [LeetCode]3Sum Closest

Share:

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.