Two Sum

1. Two Sum

167. Two Sum II - Input array is sorted

1099. Two Sum Less Than K

Solve by using TreeSet instead of map to find the max sum under K.

public int twoSumLessThanK(int[] A, int K) {
    TreeSet<Integer> set = new TreeSet<>(); 
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < A.length; i++) {
        if (set.lower(K - A[i]) != null) {
            max = Math.max(max, set.lower(K - A[i]) + A[i]);
        }
        set.add(A[i]);
    }
    return max == Integer.MIN_VALUE ? -1 : max;
}

15. 3Sum

Use if (i > 0 && nums[i] == nums[i - 1]) continue and while (left < right && nums[left] == nums[left + 1]) left++ etc to remove duplicates.

public List<List<Integer>> threeSum(int[] nums) {
    if (nums == null || nums.length < 2) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int target = -nums[i];
        int left = i + 1, right = n - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (left < right && nums[left] + nums[right] < target) {
                left++;
            } else if (left < right && nums[left] + nums[right] > target) {
                right--;
            }   
        }
    }
    return result;
}

16. 3Sum Closest

public int threeSumClosest(int[] nums, int target) {
    if (nums == null || nums.length < 2) return -1;
    Arrays.sort(nums);
    int n = nums.length;
    Integer res = null;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (res == null || Math.abs(sum - target) < Math.abs(res - target)) {
                res = sum;
            }
            if (left < right && sum < target) {
                left++;
            } else {
                right--;
            }   
        }
    }
    return res;
}

259. 3Sum Smaller

public int threeSumSmaller(int[] nums, int target) {
    int count = 0;
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            if (nums[i] + nums[left] + nums[right] < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
}

Number of Pairs Sum Greater or Equal Target

Given a sorted list of numbers and a target Z, return the number of pairs according to following definition: (X,Y) where X+Y >= Z

Example 1:

Input: arr = [1, 3, 7, 9, 10, 11], Z = 7

Output: 14

public static int numOfSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int count = 0;
    while (left < right) {
        if (nums[left] + nums[right] >= target) {
            count += right - left;
            right--;
        } else {
            left++;
        }
    }
    return count;
}

18. 4Sum

170. Two Sum III - Data structure design

653. Two Sum IV - Input is a BST

4Sum / kSum

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    return kSum(nums, 0, 4, target);
}

private List<List<Integer>> kSum (int[] nums, int start, int k, int target) {
    int len = nums.length;
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(k == 2) { //two pointers from left and right
        int left = start, right = len - 1;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum == target) {
                List<Integer> path = new ArrayList<Integer>();
                path.add(nums[left]);
                path.add(nums[right]);
                res.add(path);
                while(left < right && nums[left] == nums[left + 1]) left++;
                while(left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) { //move left
                left++;
            } else { //move right
                right--;
            }
        }
    } else {
        for(int i = start; i < len - (k - 1); i++) {
            if(i > start && nums[i] == nums[i - 1]) continue;
            List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
            for(List<Integer> t : temp) {
               t.add(0, nums[i]);
            }                    
            res.addAll(temp);
        }
    }
    return res;
}