3SUM Smaller

Question

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.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Analysis

This question is quite similar to 3SUM. we can use the same approach to solve this problem, the only difference is how we conduct the binary search process. Since we need only calculate the number of different triplets, we can use an number sum to record different cases.

There are two situations we may encounter doing binary search.

When A[j]+A[k]<target-nums[i], there are k-j different triplets satisfy the condition,we proceed by increase j;

when A[j]+A[k]>target-nums[i], we proceed by decrease k

Solution

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

        int result = 0;
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    result += (k - j);
                    j++;
                } else k--;
            }
        }

        return result;
    }
}