三数之和-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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

通过部分测试用例

这里去重要注意两个指针移动过程中也要去重！
更正代码：

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24