ThreeSumSmaller.java

ThreeSumSmaller.java

import java.util.Arrays;

/**
 * Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n
 * that satisfy the condition nums[i] + nums[j] + nums[k] < target.
 * <p>
 * For example, given nums = [-2, 0, 1, 3], and target = 2.
 * Return 2. Because there are two triplets which sums are less than 2:
 * <p>
 * [-2, 0, 1]
 * [-2, 0, 3]
 */

public class ThreeSumSmaller {

    //Very similar to 3 sum approach.
    //Other than the difference in counting the number of sums;
    

    public int threeSumSmaller(int[] nums, int target) {
        if (nums.length < 3 || nums == null) {
            return 0;
        }
        int count = 0;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    //
                    /**This is really the key difference.
                     * Simply doing count++ wont suffice.
                     * For eg in the given input, that will cause you to miss -2,0,1
                     * The underlying understanding here is KEY
                     * IF nums[i]+ nums[left]+ nums[right] < target.
                     * THEN IT IMPLIES THAT for that i ,sum  will always be less than target
                     * for all values of left and right, so we need to make sure to get the values of sums less
                     * than target for this specific left and another right(thats less than the current right)
                     * ie. -2,0,3 and then -2,0,1 for example.
                     */
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }

        return count;

    }
}