BinarySearch 0806 Sum of Two Numbers Less Than Target

Problem statement

https://binarysearch.com/problems/Sum-of-Two-Numbers-Less-Than-Target/

Solution

Equal to Leetcode 1099 Two Sum Less Than K, be careful here with negative numbers.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, k):
        nums = sorted(nums)
        beg, end, ans = 0, len(nums) - 1, -float("inf")
        while beg < end:
            if nums[beg] + nums[end] >= k:
                end -= 1
            else: 
                ans = max(ans, nums[beg] + nums[end])
                beg += 1
                
        return ans