LeetCode Q12 3 sum

Posted on In Valine:
Symbols count in article: 947 Reading time ≈ 1 mins. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution
{
    public List<List<Integer>> threeSum(int[] nums)
    {
        //1.Sort array
        Arrays.sort(nums);
        //2. Creat a double Linkedlist
        List<List<Integer>> res = new LinkedList<>();
        for(int i = 0; i < nums.length - 2; i++)
        {
            //3. if i = 0 or the 2nd number is not equal to previous number
            //为了保证不加入重复的 list,因为是有序的，所以如果和前一个元素相同，只需要继续后移就可以
            if(i == 0 || (i > 0 && nums[i] != nums[i - 1]))
            {
                 //两个指针,并且头指针从i + 1开始，防止加入重复的元素
                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
                while(lo < hi)
                {
                    if(nums[lo] + nums[hi] == sum)
                    {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while(lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        while(lo < hi && nums[hi] == nums[hi - 1]) hi--;
                        lo++;
                        hi--;
                    }
                    else if(nums[lo] + nums[hi] < sum) lo++;
                    else hi--;
                    
                }
            }
        }
        return res;
    }
}