三数之和-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;}
}