We first sort the array. Then we use `ptr1`

, `ptr2`

and `ptr3`

to point to our three numbers. The idea is similar to 3Sum: `ptr1`

goes through the array from begin to end, while `ptr2`

(starting at `ptr1 + 1`

) and `ptr3`

(starting at array end) move to each other till they meet.

The difference is that, we first keep `ptr1`

and `ptr2`

fixed, and keep moving `ptr3`

so long as the three sum is larger than or equal to target. Once it moves to a position where the three sum is smaller than target, we immediately know that if `ptr3`

keeps moving left, all the rest three sums will also be smaller than target. Therefore, we immediately add the number of three sums to the result without actually moving `ptr3`

. `ptr3`

remains at the position where the three sum is first seen smaller than target. After that, we move `ptr2`

right by one position. Now we can keep moving `ptr3`

to the left, as said above.

Since `ptr3`

never goes back and `ptr2 < ptr3`

, the above step takes time O(n). With `ptr1`

going through the array once, the overall running time is O(n^2).

```
int threeSumSmaller(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int count = 0;
for (int ptr1 = 0; ptr1 < nums.size(); ptr1++) {
int ptr3 = nums.size() - 1;
for (int ptr2 = ptr1 + 1; ptr2 < nums.size(); ptr2++) {
while (ptr2 < ptr3 && nums[ptr1] + nums[ptr2] + nums[ptr3] >= target)
ptr3--;
if (ptr3 > ptr2)
count += ptr3 - ptr2;
}
}
return count;
}
```