LeetCode刷题笔记 15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 。找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

总结

剪枝,left和right

Sample Code

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length == 0) return result; Arrays.sort(nums); for (int k = 0; k < nums.length; k++) { if (nums[k] > 0) break; if (k > 0 && nums[k] == nums[k - 1]) continue;//重复,剪枝 int target = 0 - nums[k]; //简化问题 int i = k + 1; int j = nums.length - 1; while (i < j) { if (nums[i] + nums[j] == target) { List<Integer> r = new ArrayList<>(); r.add(nums[k]); r.add(nums[i]); r.add(nums[j]); result.add(r); while (i < j && nums[i] == nums[i + 1]) ++i; while (i < j && nums[j] == nums[j - 1]) --j; ++i; --j; } else if (nums[i] + nums[j] < target) ++i; else --j; } } return result; } }

ERROR Code

class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); find(0, new ArrayList<>(), 0, res, nums); return res; } private void find(int sum, List<Integer> list, int start, List<List<Integer>> res, int[] nums) { if(list.size() == 3 && sum == 0) res.add(new ArrayList<>(list)); for(int i = start; i < nums.length; i++) { if(i > start && nums[i] == nums[i-1]) continue; list.add(nums[i]); find(sum+nums[i], list, i+1, res, nums); list.remove(list.size()-1); } } }

ERROR Code 2

class Solution { public List<List<Integer>> threeSum(int[] nums) { if(nums == null || nums.length < 3) return new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); int len = nums.length; if(nums[0] <= 0 && nums[len-1] >= 0) { for(int i = 0; i < len-2; ) { if(nums[i] > 0) break; int left = i+1; int right = len-1; do { if(left >= right || nums[i] * nums[right] > 0) break; int temp = nums[i] + nums[left] + nums[right]; if(temp == 0) { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[left]); list.add(nums[right]); res.add(list); } if(temp < 0) while(left < right && nums[left] == nums[++left]) {} else while(left < right && nums[right] == nums[--right]) {} }while(left < right); while(i < len-1 && nums[i] == nums[++i]) {} } } return res; } }