LeetCode 0016 - 3Sum Closest
# Hints
- 思维 + 双指针扫描
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array of integers and an integer , find three integers in such that the sum is closest to . 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).
# 题意
给定一个长为 的数组,给定一个整数 ,求出一个三元组 ,满足 和 的差的绝对值最小。输入数据保证有且仅有一个最优解。
# 题解
本题类似于Leetcode 0015,仍可用类似的方法解决,只是细节上有所差别。
类似地,我们仍然是先对数组排序,然后暴力枚举一个数 ,再在 的范围内对 求解2-sum问题。
我们不再需要进行去重,并且在双指针扫描的过程中,递进的判断条件有所改变。此外,思维逻辑和代码实现的主干框架基本一致,因而不再过多赘述。
细节问题:
注意2-sum的双指针扫描实现中,不要忘记特殊处理 的情况,处理不当可能会导致死循环。
更新答案时,要分别维护当前最小差值和当前答案,不要混淆。
# AC代码
class Solution {
public:
int threeSumClosest(vector<int> & nums, int target) {
// 排序
sort(nums.begin(), nums.end());
// 暴力枚举
int mindelta = INF;
int res = INF;
for (int i = 0; i < (int)nums.size() - 2; i ++) {
// 求解
int sum = nums[i] + twoSumClosest(nums, i, target - nums[i]);
// 更新答案
if (mindelta > abs(target - sum)) {
mindelta = abs(target - sum);
res = sum;
}
}
// 返回
return res;
}
// 求解2-sum-closest问题(有序)
int twoSumClosest(vector<int> & nums, int index, int target) {
// 主循环
int mindelta = INF;
int res = INF;
int left = index + 1, right = nums.size() - 1;
while (left < right) {
// 求和
int sum = nums[left] + nums[right];
// 更新答案
if (mindelta > abs(target - sum)) {
mindelta = abs(target - sum);
res = sum;
}
if (mindelta == 0) {
break;
}
// 递进
if (sum < target) left ++;
if (sum > target) right --;
}
// 返回
return res;
}
// 常量
const int INF = 0x3f3f3f3f;
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01