Leetcode-15-3Sum

3Sum

leetcode: https://leetcode.com/problems/3sum/

Description:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets

Idea:

**solution:two poiners **

Step1: sort the array(to the verify the sum), and create the array list

Step2: use first index to traverse the nums, because this nums array has been sorted, if current element it pointed bigger than 0, it means another two element will >0, the sum of theme can’t meet the requirement, return the current result. At the same time, if this element is equal to it’s next element, we skip next element to avoid the repeated combiantion in the result.

Step3: to set two pointers to get the bound of another two elements. Because the array is sorted, so if the sum >0, we need to move the right index to it’s previous poisiton to make the sum smaller. if sum< 0 , then move the left pointer to the next.

Step4: if the sum =0, record this combination, and use while loop to skip the continous same element of the left and right side to avoid repeated combinations in the result. Then, narrowing the bound to search next combination.

​

Code:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //sort the array, so more easier to adjust the index range by verifing the sum
        Arrays.sort(nums);
        //create list to store result array
        List<List<Integer>> result = new ArrayList<>();
        
        //use the first index to traverse array
        for(int i=0; i<nums.length; i++){
            //because the array ahs been sorted, and the sum should be 0, if the current element and next element both >0, it can't meet the quirement
           if(nums[i]>0){
               return result;
           }
            //avoid repeated result
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //set two pointer to get all possible combination
            int l_index=i+1;
            int r_index = nums.length-1;
            while(l_index < r_index){
                int sum = nums[i] + nums[l_index] + nums[r_index];
                //sum>0
                if(sum>0){
                    r_index--;
                }
                //sum<0
                else if(sum<0){
                    l_index++;
                }
                //sum ==0
                else{
                    //add current combination array to list
                    result.add(Arrays.asList(nums[i], nums[l_index], nums[r_index]));
                    //avoid repeated result(if current index meet the rquirement, and next element is same, skip it)
                    while(l_index<r_index && nums[l_index] == nums[l_index+1]){
                        l_index++;
                    }
                    while(l_index<r_index && nums[r_index] == nums[r_index-1]){
                        r_index--;
                    }
                    //remove left and right index to adjust the range
                    l_index++;
                    r_index--;
                }
            }
        }
        return result;
    }
}