LeetCode 3Sum-Closest

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 > 例如,给定数组 nums = [-1,2,1,-4], 和 target = 1. > > 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解答:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
sort(nums.begin(), nums.end());

int res = 0, dis = 0xffffff;
for (int i = 0; i < len - 2; i++) {
int st = i + 1, ed = len - 1;
while (st < ed) {
int sum = nums[i] + nums[st] + nums[ed];
int tmp = sum - target;
if (tmp == 0)
return target;
tmp < 0 ? ++st : --ed;
if (abs(tmp) < dis) {
dis = abs(tmp);
res = sum;
}
}
}
return res;
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×