Leetcode–4Sum

The Problem:

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

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

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

Notes:

  1. Fix two 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. See 3 Sum.

Java Solution:

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new  ArrayList<ArrayList<Integer>>();
        HashSet<String> set = new HashSet<String>(); // ---!!!!---use set to store result, remove duplicate
        if(num==null || num.length < 4)return (List)result; 
        Arrays.sort(num);
        int len = num.length;
        for(int s1 = 0; s1<len; s1++){ // ---!!!!!!-----four numbers are in order, inner loop start from the outter loop index +1
            for(int s2 = s1+1; s2<len; s2++){
                int i = s2+1;
                int j = len-1;
                int tar = target - num[s1] - num[s2];
                while(i<j){
                    if(num[i] + num[j] == tar){
                        String str = ""+num[s1]+num[s2]+num[i]+num[j];
                        if(!set.contains(str)){
                            ArrayList<Integer> one = new ArrayList<Integer>();
                            one.add(num[s1]);
                            one.add(num[s2]);
                            one.add(num[i]);
                            one.add(num[j]);
                            result.add(one);
                            set.add(str);
                            
                        }
                        i++;  //------!!!!!!!---if already get a target, i and j move at same time, 
                                    //          since only change i or j cannot produce same sum target
                        j--;
                    }
                    else if(num[i] + num[j] < tar)
                        i++;    // smaller then move right
                    else
                        j--;
                }
            }
        }
        return (List)result;
    }
}
Advertisements

Leetcode–3Sum Closest

The Problem:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 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. See 3 Sum.
  2. Record the minimum difference and result.

Java Solution:

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        Arrays.sort(num);
        int minDiff = Integer.MAX_VALUE;
        int result = 0;
        for(int first = 0; first< num.length-2; first++){
            int tar = target-num[first];
            int i = first+1;
            int j = num.length-1;
            while(i< j){
                if(num[i]+num[j]==tar)
                    return target;
                else if(num[i] + num[j] < tar){
                    if(tar-num[i]-num[j] < minDiff){
                        minDiff = tar-num[i]-num[j];
                        result = num[first] + num[i]+num[j];
                    }
                    i++;
                }
                else if(num[i] + num[j] > tar){
                    if(num[i]+num[j]-tar < minDiff){
                        minDiff = num[i]+num[j]-tar;
                        result = num[first] + num[i]+num[j];
                    }
                    j--;
                }
            }
        }
        return result;
    }
}

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;
    }
}