1099. Two Sum Less Than K 🔒

Description

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: nums = [10,20,30], k = 15
Output: -1
Explanation: In this case it is not possible to get a pair sum less that 15.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= 2000

Solutions

Solution 1: Sorting + Binary Search

We can first sort the array \(nums\), and initialize the answer as \(-1\).

Next, we enumerate each element \(nums[i]\) in the array, and find the maximum \(nums[j]\) in the array that satisfies \(nums[j] + nums[i] < k\). Here, we can use binary search to speed up the search process. If we find such a \(nums[j]\), then we can update the answer, i.e., \(ans = \max(ans, nums[i] + nums[j])\).

After the enumeration ends, return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoTypeScript

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = -1
        for i, x in enumerate(nums):
            j = bisect_left(nums, k - x, lo=i + 1) - 1
            if i < j:
                ans = max(ans, x + nums[j])
        return ans

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = -1;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            int j = search(nums, k - nums[i], i + 1, n) - 1;
            if (i < j) {
                ans = Math.max(ans, nums[i] + nums[j]);
            }
        }
        return ans;
    }

    private int search(int[] nums, int x, int l, int r) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = -1, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int j = lower_bound(nums.begin() + i + 1, nums.end(), k - nums[i]) - nums.begin() - 1;
            if (i < j) {
                ans = max(ans, nums[i] + nums[j]);
            }
        }
        return ans;
    }
};

func twoSumLessThanK(nums []int, k int) int {
    sort.Ints(nums)
    ans := -1
    for i, x := range nums {
        j := sort.SearchInts(nums[i+1:], k-x) + i
        if v := nums[i] + nums[j]; i < j && ans < v {
            ans = v
        }
    }
    return ans
}

function twoSumLessThanK(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = -1;
    for (let i = 0, j = nums.length - 1; i < j; ) {
        const s = nums[i] + nums[j];
        if (s < k) {
            ans = Math.max(ans, s);
            ++i;
        } else {
            --j;
        }
    }
    return ans;
}

Solution 2: Sorting + Two Pointers

Similar to Solution 1, we can first sort the array \(nums\), and initialize the answer as \(-1\).

Next, we use two pointers \(i\) and \(j\) to point to the left and right ends of the array, respectively. Each time we judge whether \(s = nums[i] + nums[j]\) is less than \(k\). If it is less than \(k\), then we can update the answer, i.e., \(ans = \max(ans, s)\), and move \(i\) one step to the right, otherwise move \(j\) one step to the left.