K Sum

K-SUM

2 Sum

Two Sum

One pass, Set (Map): O(n)

Two Sum II - Input array is sorted

Two pointers: O(n)

Two Sum Less Than K

Binary Search

Count the Number of Fair Pairs

public long countFairPairs(int[] nums, int lower, int upper) {
    Arrays.sort(nums);

    return binarySearch(nums, upper) - binarySearch(nums, lower - 1);
}

private long binarySearch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    long pairs = 0;
    while (low < high) {
        if (nums[low] + nums[high] <= target) {
            // (low, high) is a valid pair
            pairs += high - low++;
        } else {
            high--;
        }
    }
    return pairs;
}

3 Sum

3Sum

Sort + O(n) * Two pointers: O(n ^ 2)

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);

    int n = nums.length;
    List<List<Integer>> list = new ArrayList<>(); 
    for (int i = 0; i < n - 2; i++) {
        // the array is sosrted
        if (nums[i] > 0) {
            break;
        }

        // skips duplicates
        if (i == 0 || (i > 0 && nums[i - 1] != nums[i])) {
            int left = i + 1, right = n - 1, sum = -nums[i];
            while (left < right) {
                if (nums[left] + nums[right] == sum) {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // skips duplicates
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right - 1] == nums[right]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (nums[left] + nums[right] < sum) {
                    left++;
                } else {
                    right--;
                }
           }
        }
    }
    return list;
}

3Sum Smaller

3Sum Closest

Two pointers

3Sum With Multiplicity

private static final int MOD = (int)1e9 + 7;

public int threeSumMulti(int[] arr, int target) {
    long[] c = new long[101];
    for (int a : arr) {
        c[a]++;
    }

    long num = 0;
    for (int i = 0; i < c.length; i++) {
        for (int j = i; j < c.length; j++) {
            int k = target - i - j;
            if (k >= c.length || k < 0) {
                continue;
            }

            if (i == j && j == k) {
                num += c[i] * (c[i] - 1) * (c[i] - 2) / 6;
            } else if (i == j && j != k) {
                num += c[i] * (c[i] - 1) / 2 * c[k];
            } else if (j < k) {
                num += c[i] * c[j] * c[k];
            }
        }
    }
    return (int)(num % MOD);
}

Valid Triangle Number

K Sum

O(n ^ (k - 1))

• Sort + O(n ^ (k - 2)) * Two pointers
• O(n ^ (k - 2)) * Set/Map

public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
    int n = nums.length;
    List<List<Integer>> list = new ArrayList<>();
    if (start == n || nums[start] * k > target || target > nums[n - 1] * k) {
        return list;
    }

    if (k == 2) {
        return twoSum(nums, target, start);
    }

    for (int i = start; i < n; i++) {
        if (i == start || nums[i - 1] != nums[i]) {
            for (var set : kSum(nums, target - nums[i], i + 1, k - 1)) {
                list.add(new ArrayList<>(Arrays.asList(nums[i])));
                list.get(list.size() - 1).addAll(set);
            }
        }
    }

    return list;
}

4Sum II

O(n ^ 2)

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int c : C) {
        for (int d : D) {
            map.compute(c + d, (k, v) -> v == null ? 1 : v + 1);
        }
    }

    int count = 0;
    for (int a : A) {
        for (int b : B) {
            count += map.getOrDefault(-a - b, 0);
        }
    }
    return count;
}

Split Array with Equal Sum

O(n ^ 2):

(0, i), (i, j) + Set; (j, k), (k, n)

Closest

Closest Subsequence Sum

public int minAbsDifference(int[] nums, int goal) {
    int n = nums.length;
    Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>();

    // generates all possible sums of the first and second half
    backtrack(nums, 0, n / 2, 0, set1);
    backtrack(nums, n / 2, n, 0, set2);

    // sorts the possible sums of the second half
    List<Integer> sums2 = new ArrayList<>(set2);
    Collections.sort(sums2);

    // for each possible sum of the first half
    // finds the sum in the second half that gives a value closest to the goal using binary search
    // initial value is choosing none from nums
    int min = Math.abs(goal);
    for (int sum1 : new ArrayList<>(set1)) {
        int sum2 = goal - sum1;

        // binary search
        int index = Collections.binarySearch(sums2, sum2);
        if (index < 0) {
            index = ~index;
            if (index < sums2.size()) {
                min = Math.min(min, Math.abs(sum2 - sums2.get(index)));
            }
            if (index > 0) {
                min = Math.min(min, Math.abs(sum2 - sums2.get(index - 1)));
            }
        } else {
            // found exact match
            return 0;
        }

        if (min == 0) {
            break;
        }
    }
    return min;
}

private void backtrack(int[] nums, int start, int end, int sum, Set<Integer> sums) {
    if (start == end) {
        sums.add(sum);
        return;
    }

    backtrack(nums, start + 1, end, sum, sums);
    backtrack(nums, start + 1, end, sum + nums[start], sums);
}