三数之和【LC15】
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请
你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
排序+双指针
- 思路
- 首先对数组进行排序，然后遍历数组，在确定
nums[i]的情况下，在数组nums[i+1,n-1]中使双指针法（前后指针），确定另外两个元素，判断这三个元素之和sum与target的大小：
- 如果
nums[i] + nums[left] + nums[right] > 0,说明right下标应该向左移动
去重：while (left < right && nums[right] == nums[right + 1]) right--;【非必须】 - 如果
nums[i] + nums[left] + nums[right] < 0,说明left下标应该向右移动
去重：while (left < right && nums[left] == nums[left - 1]) left++;【非必须】
如果nums[i] + nums[left] + nums[right] == 0,说明找到了三元组，双指针同时收缩，right--；left++
去重： while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++){ if (nums[i] > 0){ return res; } if (i > 0 && nums[i] == nums[i-1] ){ continue; } int left = i + 1; int right = nums.length - 1; while (left < right){ int sum = nums[i] + nums[left] + nums[right]; if (sum > 0){ right--; // 非必须 while(left < right && nums[right] == nums[right+1]){ right--; } }else if (sum < 0){ // 非必须 left++; while (left < right && nums[left-1] == nums[left]){ left++; } }else{ res.add(Arrays.asList(nums[i],nums[left],nums[right])); while(left < right && nums[right] == nums[right-1]){ right--; } while (left < right && nums[left+1] == nums[left]){ left++; } right--; left++; } } } return res; } }
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int len = nums.length; int i = 0; while (i < len - 2){ twoSum(nums,i,res); int temp = nums[i]; while (i < len && temp == nums[i]){ i++; } } return res; } public void twoSum(int[] numbers, int i, List<List<Integer>> res ) { int len = numbers.length; int left = i + 1; int right = len - 1; while(left < right){ if ( numbers[i] + numbers[left] + numbers[right] == 0){ res.add(Arrays.asList(numbers[i],numbers[left],numbers[right])); int temp = numbers[left]; while (numbers[left] == temp && left < right){ left++; } }else if(numbers[i] + numbers[left] + numbers[right] > 0){ right--; }else { left++; } } } }
