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:

for i in range(len(arr)):
    for j in range(i+1, len(arr)): # j greater than i
        a = arr[i]
        b = arr[j]

        c = # the biggest value that's less than `target - a - b`

        # update biggest `a + b + c` seen

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:

def threeSumSmaller(arr, target):

    arr.sort()

    # finds the biggest value that's less than `high`
    def binarySearch(i, j, high):
        val = float('-inf')
        while i <= j:
            mid = (i + j) // 2
            if arr[mid] < high:
                val = arr[mid]
                i = mid + 1
            else:
                j = mid - 1
        return val
 
    biggestSum = float('-inf')
    
    for i in range(1,len(arr)):
        for j in range(i+1, len(arr)):
            a = arr[i]
            b = arr[j]

            # the biggest value that's less than `target - a - b`
            c = binarySearch(0, i - 1, target - a - b)

            # update biggest `a + b + c` seen
            biggestSum = max(biggestSum, a + b + c)

    return biggestSum

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.