TwoSum

1. 2 Sum

Return the indexes of sum equals to target 1. Hash table (target-num, index) 2. If we can find num in hash table, return

2 Sum Closest

2 numbers sum up closest to target, return the diff

• sort array

public int twoSumClosest(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return -1;
    }

    Arrays.sort(nums);

    int left = 0, right = nums.length - 1;
    int diff = Integer.MAX_VALUE;

    while (left < right) {
        if (nums[left] + nums[right] < target) {
            diff = Math.min(diff, target - (nums[left] + nums[right]));
            left++;
        } else {
            diff = Math.min(diff, nums[left] + nums[right] - target);
            right--;
        }
    }

    return diff;
}

15. 3 sum

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.

• Apply 2sum

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);
    for(int i=0; i<nums.length-2; i++){
        if(i==0 || nums[i] != nums[i-1]){
            int start = i+1;
            int end = nums.length-1;
            int target = 0 - nums[i];
            while(start<end){
                if(nums[start] + nums[end] == target){
                    ans.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    end--;
                    while(start<end && nums[start] == nums[start-1]) start++;
                    while(start < end && nums[end] == nums[end+1]) end--;
                }else if(nums[start] + nums[end] < target){
                    start++;
                }else{
                    end--;
                } 
            }
        }
    }
    return ans;
}

16. 3 Sum Closest

Return the closest sum of integers

public int threeSumClosest(int[] numbers, int target) {
    int ans = nums[0]+nums[1]+nums[2];
    Arrays.sort(numbers);
    for (int i = 0; i < numbers.length - 2; i++){
        int j = i+1, k = numbers.length - 1;
        while(j < k){
            int sum = numbers[i] + numbers[j] + numbers[k];
            if (Math.abs(target - sum) < Math.abs(target - ans)){
                ans = sum;
            }

            if (sum < target){
                j++;
            }else{
                k--;
            }
        }
    }
    return ans;
}

18. 4 Sum

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

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(nums);

    for(int i=0; i<nums.length-3; i++){
        if(i>0 && nums[i] == nums[i-1]) continue;
        for(int j=i+1; j<nums.length-2; j++){
            if(j >i+1 && nums[j] == nums[j-1]) continue;
            int target2 = target - nums[i] - nums[j];
            int start = j+1, end=nums.length-1;
            while(start<end){
                if(nums[start]+nums[end] == target2){
                    ans.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
                    start++;
                    end--;
                    while(start<end && nums[start-1] == nums[start]) start++;
                    while(start<end && nums[end+1] == nums[end]) end--;
                }else if(nums[start]+nums[end]<target2){
                    start++;
                }else{
                    end--;
                }
            }      
        } 
    }
    return ans;
}

4 Sum ll

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

1. Count the combination of a+b, n^2 loop, Hash table<-sum, times>

2. Check if c+d match and a+b match target, n^2 loop, count the sum of times

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<A.length; i++){
        for (int j=0; j<B.length; j++){
            int sum = A[i] + B[j];
            if (map.containsKey(-sum)){
                 map.put(-sum, map.get(-sum)+1);
            }else{
                map.put(-sum, 1);
            }
        }
    }

    int ans = 0;
    for (int i=0; i<C.length; i++){
        for (int j=0; j<D.length; j++){
            int sum = C[i] + D[j];
            if (map.containsKey(sum)){
                ans += map.get(sum);
            }
        }
    }
    return ans; 
}

Whole minute dilemma

Given a list of song length, return the number of ways choose 2 songs that the total duration is multiple of whole minute.

• remain = second % 60

• residue = 60 - remaon

• Map

private List<List<Integer>> minuteDilemma(int[] songs){
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, List<Integer>> map = new HashMap<>();
    for(int i =0; i< songs.length; i++){
        int remain = songs[i]%60;

        // put every pair in answer
        if(map.containsKey(remain)){
            for(int index: map.get(remain)) {
                ans.add(Arrays.asList(new Integer[]{songs[index], songs[i]}));
            }
        }

        // update hash table
        int residue = 60 - remain;
        if(!map.containsKey(residue)) map.put(residue, new ArrayList<>());
        List<Integer> tmp = map.get(residue);
        tmp.add(i);
        map.put(residue, tmp);
    }
    return ans;
}

public static void main(String[] args){
    int[] t = new int[] {58 ,2, 62, 118};
    minuteDilemma min = new minuteDilemma();

    System.out.println(min.minuteDilemma(t));
}

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

• Inorder traverse to a list

public boolean findTarget(TreeNode root, int k) {
    List<Integer> list = new ArrayList<>();
    inorder(root, list);

    int i=0, j=list.size()-1;
    while(i<j){
        int sum = list.get(i)+list.get(j);
        if(sum == k) return true;
        else if(sum < k) i++;
        else j--;
    }

    return false;

}

private void inorder(TreeNode root, List<Integer> list){
    if(root == null) return;
    inorder(root.left, list);
    list.add(root.val);
    inorder(root.right, list);
}