### 题目

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.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]


Follow up: Could you solve it in O(n2) runtime?

### 主要思路

 left               right
|                  |
1,2,3,4,5,6,7,8,9,10              target = 8

1 + 10 > 8      -> right--


1 + 10 > 8，这时候如果right不动，left1-9的9种可能都排除了，都太大。只能right左移。

 left               right
|                  |
1,2,3,4,5,6,7,8,9,10              target = 15

1 + 10 < 15      -> left++


1 + 10 < 15，这时候如果left不动，right2-10的9种可能都排除了，都太小。只能left右移。

### 朴素遍历，$O(n^3)$

#### 代码

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


### Two Pointers法, $O(n^2)$

  i left           right
|  |              |
[-3,-1,1,5,8,11,15,16]          target = 10


(-3) + (-1) + 16 > 10，太大了。所有left再往左移的情况都不用再考虑了，因为只会更大。所以right往左移。取更小的值。

  i left    right
|  |       |
[-3,-1,1,5,8,11,15,16]          target = 10


     i left        right
|  |           |
[-3,-1,1,5,8,11,15,16]          target = 10


#### 代码

public class Solution {
public int threeSumSmaller(int[] nums, int target) {
if (nums.length < 3) { return 0; }
Arrays.sort(nums);
int count = 0;
for (int i = 0; i < nums.length-2; i++) {
int left = i+1, right = nums.length-1;
while (left < right) {
if (nums[i] + nums[left] + nums[right] < target) {
count += (right - left); left++;
} else {
right--;
}
}
}
return count;
}
}