In this problem, we want to find 3 numbers whose total is smaller than the target:

When you solve problems like this, you should always write one variable using the other variables. You can subtract b and c from both sides of the equation to get this equation:

This equation means that c depends fully on a and b, so you don't have to loop over c. You only have to loop over a and b. Here's the pseudocode for the solution:

To avoid visiting different permuations of the same exact a, b, and c multiple times, we can make sure that c is to the left of a.

To find c, we want to find the biggest element less than target - a - b. Finding the biggest element less than a value (or vice versa) is the main purpose of binary search, so we'll use binary search to find c. This takes $O(\log n)$ time. To do binary search, we also need to sort the array at the start, but this takes $O(n \log n)$ time and is negligible. The binary search bounds should be 0 to i-1, since c must be to the left of a. Here's the code for this:

Time Complexity $O(n^2 \log n)$. The double for-loop does O(n$^2$) iterations, and each iteration does a binary search which takes O(log n) time.

We also sort the array at the very beginning, which takes $O(n \log n)$. This is is insignificant compared to the other $O(n^2 \log n)$ term.

Space Complexity $O(1)$. We only have to store 2 variables, which is O(2) = O(1). The size of the input is never included in the space complexity, so the array does not contribute to the space complexity.