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

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

Leetcode–Substring with Concatenation of All Words

The Problem:

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Notes:

  1. Use a hash map to store word and its occurrence.
  2. Two pointers: start and end, to record from each start if can reach an end that covers all words in L.
  3. Attention to the for loop conditions, optimize the ending condition to cut the unnecessary iterations.
  4. Mistake I made: each time change a new start, map and got need to be reinitialized.

Java Solution:

public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> ind = new ArrayList<Integer>();
        if(L.length==0)return ind;
        int len = L[0].length();
        HashMap<String, Integer> map = new HashMap<String,  Integer>();
        for(int i = 0; i < L.length; i++){
            if(map.containsKey(L[i])){
                int t = map.get(L[i]);
                map.put(L[i], t+1);
            }
            else{
                map.put(L[i], 1);
            }
        }
        
        for(int start = 0; start <= S.length()-L.length *len; start++){
            //--!! iteration can stop when not enough word from start to cover all in L
            HashMap<String, Integer>  tmpmap = new HashMap<String, Integer>(map);
            int got = 0; //--!! each new start needs to reset got
            for(int i = start; i <= start + (L.length-1) * len; i=i+len){
                //--!!check the bundary before call substring
                if(i+len > S.length())
                    break;
                String sub = S.substring(i, i+len);
                if(tmpmap.containsKey(sub)){
                    got++;
                    int c = tmpmap.get(sub);
                    if(c>1)
                        tmpmap.put(sub, c-1);
                    else
                        tmpmap.remove(sub);
                }
                else{
                    break;
                }
            }
            if(got == L.length){
                ind.add(start);
            }
        }
        return ind;
    }
}

Java Solution II :

I came up with another solution, which reduced execution time a lot, but code is not that straightforward and concise.

  1. Traverse the string by chunks of word length in L (len), two pointers (start and end) always advance by len. In the out-most loop, iterate all possibility of starting point in S, (0,1,…len-1)
  2. Start and end pointer forms a sliding window:
    1. Each time find a match, end pointer advance. If the number of match reaches L.length, add back the start word to map, decrease number of match, then move start to next, and in next iteration see if end can form another valid window.
    2. Each time find a mismatch, while start < end, add back the start word to map, move start forward to next word, and decrease the number of match, decrease end to check for the same word again in next iteration. Because there are cases that end exists in the original map, but previous traversed end has the same value and already removed that word from map.
  3. Again each time start move to next, check if the remaining characters from start enough for all the words in L.
public class Solution {
    public List<Integer> findSubstring(String S, String[] L) {
        if(S.length()==0 || L.length==0)return null;
        // create a hash table for L
        HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
        for(String str : L){
            if(Lmap.containsKey(str)){
                int c = Lmap.get(str);
                Lmap.put(str,c+1);
            }
            else
                Lmap.put(str, 1);
        }
        List<Integer> result = new ArrayList<Integer>();
        int start = 0;
        int len = L[0].length();
 
        int match = 0;
        HashMap<String, Integer> map = new HashMap<String, Integer>(Lmap);
        for(int j = 0; j < len; j++){
            start = j;
            for(int i = j; i+len <= S.length(); i+=len){
                String sub = S.substring(i, i+len);
                if(map.containsKey(sub)){
                    match++;
                    int c = map.get(sub);
                    if(c>1)
                        map.put(sub, c-1);
                    else
                        map.remove(sub);
                         
                    if(match==L.length){
                        result.add(start);
                    // start advance for one word, if that word found in next i, then found another complete match
                        match--;
                        if((start+len * L.length) <= S.length()){
                            map.put(S.substring(start, start+len), 1);
                            start = start+len;
                        }
                        else
                            break;
                    }
                }
                else{
                    // mismatch, reset start, map and match
                    match--;
                    if((start+len * L.length)<= S.length()){
                        if(start<i){
                            map.put(S.substring(start, start+len), 1);
                            start = start+len;
                            i-=len;
                        }
                        else{
                            map = new HashMap<String, Integer>(Lmap);
                            match = 0;
                            start+=len;
                        }
                    }
                    else
                        break;
                }
               
            }
            match=0; // !!!---remember to reset match, and set back the start
            map = new HashMap<String, Integer>(Lmap);
        }
        return result;
    }
}