# 3Sum Smaller

Medium

Given an array ofnintegersnumsand atarget, 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`.

**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`指针。

```java
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;
    }
}
```