Fork me on GitHub

3Sum

Posted on

Preface

This is the first time to record my leetcode journey on the blog, in memory of the suffering of the disease.

Description:

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Example

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Analysis

Base: TwoSum

Background

Two Sum problem is simple, just need find all the pair in the array which satisify the sum is equal to a certain number. Here are 2 main solutions(except the bi-loop brutal way):

  1. Use a boolean map to record whether the certain number is in the given array(O(n)), then travserse the given array(O(n))
  2. Sort the given array, then use two pointer initialized at the start and the end of the array, to detect the proper pair of items by moving.

Extension: Three Sum

Two ways to solve the 3sum problem, and all needs to downgrade the 3sum to 2sum problem,

Tricky and Dirty

Getting familiar with Java do require me some time to read the reference API in Java. Als in my initial implementation, I ignore the duplication case, so I just use the set in java brutally. But the efficiency of the algo is really low, and because of it, I encountered the TLE in the second to last case.

My ugly implementation:(It do work)

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums){
        List<List<Integer>> ret = new LinkedList<>();
        Arrays.sort(nums);
        if (nums.length<3){
            return ret;
        }
        for (int i = 0; i < nums.length-2; i++){
            if(nums[i] > 0)
                break;
            else if(nums[i] == 0 && nums[i+1] == 0 && nums[i+2] == 0){
                List<Integer> triple = new LinkedList<Integer>();
                triple.add(0);
                triple.add(0);
                triple.add(0);
                ret.add(triple);
                break;
            }
            Integer two_sum = nums[i];
            two_sum = -two_sum;
            int start = i + 1;
            int end = nums.length-1;
            while(start < end){
                while(nums[start)
                if(nums[start] + nums[end] == two_sum){
                    List<Integer> triple = new LinkedList<Integer>();
                    triple.add(nums[i]);
                    triple.add(nums[start]);
                    triple.add(nums[end]);
                    ret.add(triple);
                    ++start;
                    --end;
                }else if(nums[start] + nums[end] < two_sum){
                    ++start;
                }else {
                    --end;
                }
            }
        }
        Set set = new HashSet();
        set.addAll(ret);
        List<List<Integer>> new_ret = new LinkedList<>();
        new_ret.addAll(set);
        return new_ret;
    }
}

After understanding the tricky of ignoring duplicated item by traversing the pointer(since the array has been sorted), the new code is much cleaner and faster:

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){
        List<List<Integer>> ret = new LinkedList<>();
        Arrays.sort(nums);
        if (nums.length<3){
            return ret;
        }
        for (int i = 0; i < nums.length-2; i++){
            if(nums[i] > 0)
                break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int two_sum = -nums[i];
            // two_sum = -two_sum;
            int start = i + 1;
            int end = nums.length-1;
            while(start < end){
                if(nums[start] + nums[end] == two_sum){
                    List<Integer> triple = new LinkedList<Integer>();
                    triple.add(nums[i]);
                    triple.add(nums[start]);
                    triple.add(nums[end]);
                    ret.add(triple);
                    while(end > start && nums[end-1]==nums[end]) --end;
                    while(start < end && nums[start]==nums[start+1]) ++start;
                    ++start;
                    --end;
                }else if(nums[start] + nums[end] < two_sum){
                    ++start;
                }else {
                    --end;
                }
            }
        }
        return ret;
    }
}

Result

Reference

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