# Clean C++ Solution, O(n^2)

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.