Leetcode–3Sum

The Problem:

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

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

Notes:

  1. Fix one number first, look for the two sum up to a target. The n-sum questions all follow the same idea, break down to two sum.
  2. For two sum, in a sorted array, start from first and last index, if sum less than target, means need to replace one with larger number, so first index increase, otherwise last index decrease. If match the target, then both first and last index advance a step to middle.
  3. Attention that no duplicates allowed in result, so use a Hash Set to store the triples. Use array or list in set is no good for duplication check, it will not check for the same value but the exact object. Use a concatenated string instead can do the trick.

Java Solution:

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        HashSet<String> resSet = new HashSet<String>();
        for(int first = 0; first < num.length-2; first++){
            int target = 0-num[first];
            int i = first+1;
            int j = num.length-1;
            while(i < j){
                if(num[i] + num[j]==target){
                    StringBuilder str = new StringBuilder();
                    str.append(num[first]).append(",").append(num[i]).append(",").append(num[j]);
                    if(!resSet.contains(str.toString())){
                        resSet.add(str.toString());
                        ArrayList<Integer> one = new ArrayList<Integer>();
                        one.add(num[first]);
                        one.add(num[i]);
                        one.add(num[j]);
                        result.add(one);
                    }
                    i++;
                    j--;
                }
                else if(num[i] + num[j]<target){
                    i++;
                }
                else {
                    j--;
                }
            }
        }
        return result;
    }
}
Advertisements

4 thoughts on “Leetcode–3Sum

  1. Pingback: Leetcode–3 Sum Closest | Linchi is coding

  2. Pingback: Leetcode–4 Sum | Linchi is coding

  3. Pingback: Leetcode–Two Sum | Linchi is coding

  4. Pingback: Leetcode– Sort Colors | Linchi is coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s