双指针
解题思路
对数组进行升序排序，使用三个指针 i、j 和 k 分别代表要找的三个数，通过枚举 k 确定第一个数，另外两个指针 i、j 分别从左边 k + 1 和右边 n - 1 往中间移动，找到满足
nums[i] + nums[j] + nums[k] == 0的所有组合；j 和 k 指针的移动逻辑：
sum > 0：k 左移，使 sum 变小，记录与 target 的差的绝对值，相差的小的保留下来；sum < 0：j 右移，使 sum 变大，记录与 target 的差的绝对值，相差的小的保留下来；sum = 0：直接返回；
复杂度
-
时间复杂度
O(N^2)：数组排序O(NlogN)，遍历数组+双指针遍历 O(n^2)，总体O(NlogN) + O(n^2) -
空间复杂度
O(1)
代码实现
var threeSumClosest = function (nums, target) {
let res = nums[0] + nums[1] + nums[2];
nums.sort((a, b) => a - b);
let i, j;
for (let k = 0; k < nums.length - 2; k++) {
i = k + 1;
j = nums.length - 1;
while (i < j) {
sum = nums[k] + nums[i] + nums[j];
if (Math.abs(target - sum) < Math.abs(target - res)) {
res = sum;
} else if (sum > target) {
j--;
} else if (sum < target) {
i++
} else {
return res;
}
}
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 538. 把二叉搜索树转换为累加树
上一篇
评论
