青岛网站建设设计,免费合作加工厂,教育网站建设需求分析报告,个人网站备案备注怎么写目录
LeetCode之路——15. 三数之和
分析#xff1a;
官方题解#xff1a; LeetCode之路——15. 三数之和
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nu…目录
LeetCode之路——15. 三数之和
分析
官方题解 LeetCode之路——15. 三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。 示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。
示例 2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。
示例 3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。 提示 3 nums.length 3000 -105 nums[i] 105 分析
借助1. 两数之和的思路可以让nums[i] a去遍历数组作为target。同时nums[i1] b继续遍历数组找到nums[j]满足 a b nums[j] 0.
1.需要注意元素组去重。
2.需要注意数组边界。
class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();if (nums.length 3) return res;Arrays.sort(nums); // 递增顺序for (int i 0; i nums.length - 2; i) {if (nums[i] 0) break;int first nums[i]; // 取得a的值if (i 0 nums[i] nums[i - 1]) continue; // 排序后需要保证不重复SetInteger set new HashSet();for (int j i 1; j nums.length; j) {int second nums[j]; // 取得b的值int third - (first second);if (set.contains(third)) {res.add(new ArrayList(Arrays.asList(first,second,third)));while(j nums.length - 1 nums[j] nums[j 1]) j;}set.add(second);}}return res;}
} 时间复杂度O(N^2) 空间复杂度O(N)
官方题解
class Solution {public ListListInteger threeSum(int[] nums) {int n nums.length;Arrays.sort(nums);ListListInteger ans new ArrayListListInteger();// 枚举 afor (int first 0; first n; first) {// 需要和上一次枚举的数不相同if (first 0 nums[first] nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third n - 1;int target -nums[first];// 枚举 bfor (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 后续的增加// 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if (second third) {break;}if (nums[second] nums[third] target) {ListInteger list new ArrayListInteger();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}
作者力扣官方题解
链接https://leetcode.cn/problems/3sum/solutions/284681/san-shu-zhi-he-by-leetcode-solution/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。 时间复杂度O(N^2) 空间复杂度O(N)
