1099

1099. Two Sum Less Than K (Easy)

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

Companies: Amazon, Capital One, TikTok, Facebook, turing

Related Topics:
Array, Two Pointers, Binary Search, Sorting

Similar Questions:

• Two Sum (Easy)
• Two Sum II - Input Array Is Sorted (Medium)
• 3Sum Smaller (Medium)
• Subarray Product Less Than K (Medium)

Hints:

• What if we have the array sorted?
• Loop the array and get the value A[i] then we need to find a value A[j] such that A[i] + A[j] < K which means A[j] < K - A[i]. In order to do that we can find that value with a binary search.

Solution 1. Two Pointers

// OJ: https://leetcode.com/problems/two-sum-less-than-k/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int twoSumLessThanK(vector<int>& A, int k) {
        sort(begin(A), end(A));
        int i = 0, j = A.size() - 1, ans = INT_MIN;
        while (i < j) {
            int sum = A[i] + A[j];
            if (sum < k) {
                ans = max(ans, sum);
                ++i;
            } else --j;
        }
        return ans == INT_MIN ? -1 : ans;
    }
};