先来回顾一下上期的问题及答案:
「三数之和」(3Sum)。以下是题目的描述:
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c,使得 a + b + c = 0?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例说明:
应该返回所有满足题意且不重复的三元组。
解集不能包含重复的三元组。
以下是对应的JavaScript解答:
function threeSum(nums) {const result = [];nums.sort((a, b) => a - b);for (let i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] === nums[i - 1]) {continue; // 跳过重复的数字}let left = i + 1;let right = nums.length - 1;while (left < right) {const sum = nums[i] + nums[left] + nums[right];if (sum === 0) {result.push([nums[i], nums[left], nums[right]]);while (left < right && nums[left] === nums[left + 1]) {left++; // 跳过重复的数字}while (left < right && nums[right] === nums[right - 1]) {right--; // 跳过重复的数字}left++;right--;} else if (sum < 0) {left++;} else {right--;}}}return result;
}
解题思路:
首先对数组
nums
进行排序,以便于使用双指针的方法进行查找。遍历数组
nums
,使用指针i
从左往右选取第一个数字。在每个固定的数字
nums[i]
的基础上,使用双指针left
和right
分别指向剩余数组中的左右两端。根据三个数字的和与目标值的关系进行移动指针:
如果三个数字的和等于 0,将结果添加到
result
数组中,并分别移动left
和right
指针。如果三个数字的和小于 0,移动
left
指针。如果三个数字的和大于 0,移动
right
指针。
在移动指针时,需要跳过重复的数字,以避免重复的解。
最终返回结果数组
result
。
时间复杂度分析:
数组排序的时间复杂度为 O(nlogn)。
双指针的移动最多需要遍历整个数组,时间复杂度为 O(n)。
总体时间复杂度
为 O(nlogn + n^2),简化为 O(n^2)。
空间复杂度分析:
使用了一个结果数组来存储符合条件的三元组,空间复杂度取决于结果的数量,最坏情况下为 O(n)。
2023年6月13日
「最接近的三数之和」(3Sum Closest)。以下是题目的描述:
给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 (-1 + 2 + 1 = 2) 。
解题思路:
首先对数组
nums
进行排序,以便于使用双指针的方法进行查找。初始化一个变量
closestSum
,用于记录与目标值target
最接近的三个数的和,初始值为前三个数的和。遍历数组
nums
,使用指针i
从左往右选取第一个数字。在每个固定的数字
nums[i]
的基础上,使用双指针left
和right
分别指向剩余数组中的左右两端。计算当前三个数字的和
sum
,并根据与目标值target
的差值的绝对值判断是否更新closestSum
。根据三个数字的和与目标值的关系进行移动指针:
如果三个数字的和等于
target
,则直接返回该和。如果三个数字的和小于
target
,移动left
指针。如果三个数字的和大于
target
,移动right
指针。
最终返回
closestSum
。
上面问题的答案会在第二天的公众号推文中公布,大家可以关注公众号:程序员每日三问,第一时间获得推送内容。
学习不打烊,充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题(死磕自己,愉悦大家) 希望大家在这浮夸的程序员圈里保持冷静,每天坚持花20分钟来学习与思考,在千变万化,类库层出不穷的今天,不要等到找工作时才狂刷题,提倡每日学习。