三数之和-Leetcode

leetcode链接：三数之和

题目描述

在这里插入图片描述

解题思路

主要要思考以下几个问题：

如何选取三个元素？— 当前节点 + 左指针 + 右指针
指针开始位置？— 左指针 = 当前节点位置 i + 1，右指针 = n - 1
如何保证不重复？ — 先把数组排序，再去重
如何控制指针移动？ — 排序后，左指针是最小值，右指针是最大值，根据当前三数之和的状态移动左右指针

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int n = nums.length;List<List<Integer>> res = new ArrayList<>();for(int i = 0; i < nums.length; i++) {int l = i + 1, r = n - 1;if(i > 0 && nums[i] == nums[i-1]) continue; // 去重while(l < r) {int sum = nums[i] + nums[l] + nums[r];if(sum < 0) l++;else if(sum > 0) r--;else {res.add(Arrays.asList(nums[i], nums[l], nums[r]));l++;r--;}}}return res;}
}

通过部分测试用例
在这里插入图片描述
这里去重要注意两个指针移动过程中也要去重！
更正代码：

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int n = nums.length;List<List<Integer>> res = new ArrayList<>();for(int i = 0; i < nums.length; i++) {int l = i + 1, r = n - 1;if(i > 0 && nums[i] == nums[i-1]) continue; // 去重while(l < r) {int sum = nums[i] + nums[l] + nums[r];if(sum < 0) l++;else if(sum > 0) r--;else {res.add(Arrays.asList(nums[i], nums[l], nums[r]));while(l < r && nums[l+1] == nums[l]) l++;while(l < r && nums[r] == nums[r-1]) r--;l++;r--;}}}return res;}
}