3Sum Smaller

Medium

Given an array ofnintegersnumsand atarget, find the number of index tripletsi, j, kwith0 <= i < j < k < nthat satisfy the conditionnums[i] + nums[j] + nums[k] < target.

Example:

Input:
nums
 = 
[-2,0,1,3]
, and 
target
 = 2

Output:
 2 

Explanation:
 Because there are two triplets which sums are less than 2:
             [-2,0,1]
             [-2,0,3]

Follow up: Could you solve it i nO(n^2) runtime?

Solution & Analysis

Two Pointers - Time O(n^2), Space O(1) - (4 ms, faster than 56.85%)

基本思想跟3Sum一样，不同之处在于nums[i] + nums[j] + nums[k] < target的时候，记录count += k - j，因为k在当前位置就满足smaller条件，那么一直到j + 1都可以满足，所以直接加上中间所有的可能组合；之后只移动j指针。

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1; 
            int k = nums.length - 1;

            while (j < k) {
                if (nums[i] + nums[j] + nums[k] >= target) {
                    k--;
                } else {
                    count += k - j;
                    j++;
                }
            }
        }
        return count;
    }
}