leetcode_15.三数之和/16.最接近的三数之和
2022/4/15 23:42:57
本文主要是介绍leetcode_15.三数之和/16.最接近的三数之和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
15.三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
排序 + 双指针
class Solution { public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 枚举 a for (int first = 0; first < n; ++first) { // 需要和上一次枚举的数不相同 if (first > 0 && nums[first] == nums[first - 1]) { continue; } // c 对应的指针初始指向数组的最右端 int third = n - 1; int target = -nums[first]; // 枚举 b for (int second = first + 1; second < n; ++second) { // 需要和上一次枚举的数不相同 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 需要保证 b 的指针在 c 的指针的左侧 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合,随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环 if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; } } 链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
链接:https://leetcode-cn.com/problems/3sum/
16.最接近的三数之和
排序 + 双指针
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int best = 10000000; // 枚举 a for (int i = 0; i < n; ++i) { // 保证和上一次枚举的元素不相等 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 使用双指针枚举 b 和 c int j = i + 1, k = n - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; // 如果和为 target 直接返回答案 if (sum == target) { return target; } // 根据差值的绝对值来更新答案 if (Math.abs(sum - target) < Math.abs(best - target)) { best = sum; } if (sum > target) { // 如果和大于 target,移动 c 对应的指针 int k0 = k - 1; // 移动到下一个不相等的元素 while (j < k0 && nums[k0] == nums[k]) { --k0; } k = k0; } else { // 如果和小于 target,移动 b 对应的指针 int j0 = j + 1; // 移动到下一个不相等的元素 while (j0 < k && nums[j0] == nums[j]) { ++j0; } j = j0; } } } return best; } } 链接:https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
这篇关于leetcode_15.三数之和/16.最接近的三数之和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升