LeetCode-16-最接近的三数之和
2023-03-07 09:12:15 时间
# LeetCode-16-最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示:
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
# 解题思路
方法1、回溯:
回溯穷举所有可能的排列,如果当前深度达到3,且当前sum值更接近target就更新答案res
从deep=0,sum=0,index=0开始遍历
回溯前深度+1,sum加上当前的nums[i]
回溯之后深度-1,sum减去上一轮加入的值
方法2、排序+双指针:
详见https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
# Java代码1
class Solution {
int res = 0;
public int threeSumClosest(int[] nums, int target) {
res = nums[0] + nums[1] + nums[2];
backtrace(nums, target, 0, 0, 0);
return res;
}
private void backtrace(int[] nums, int target, int deep, int sum, int index) {
if (deep == 3) {
if (Math.abs(target - res) > Math.abs(sum - target)) {
res = sum;
}
return;
}
for (int i = index; i < nums.length; i++) {
sum += nums[i];
deep++;
backtrace(nums, target, deep, sum, i + 1);
sum -= nums[i];
deep--;
}
}
}
# Java代码2
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int min = Integer.MAX_VALUE;
int ans = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int start = i + 1;
int end = len - 1;
while (start < end) {
int value = nums[i] + nums[start] + nums[end];
if (value == target) {
return value;
}
if (Math.abs(value - target) < min) {
min = Math.abs(value - target);
ans = value;
}
if (value > target) {
end--;
} else {
start++;
}
}
}
return ans;
}
}
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的