BinarySearch 0635 Sum of Three Numbers Less than Target

Problem statement

https://binarysearch.com/problems/Sum-of-Three-Numbers-Less-than-Target/

Solution

Equal to Leetcode 0259. 3Sum Smaller.

Complexity

Time complexity is O(n^2), space is O(n).

Code

class Solution:
    def solve(self, nums, target):
        nums.sort()
        n, ans = len(nums), 0
        
        for i in range(n-2):
            goal = target - nums[i]
            beg, end = i + 1, n - 1

            while beg < end:
                if nums[beg] + nums[end] >= goal:
                    end -= 1
                else: 
                    ans += (end - beg)
                    beg += 1
                
        return ans