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 <= 1001 <= nums[i] <= 10001 <= 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 × log n), and the space complexity is O(log n). Here, n is the length of the array nums.
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(code-box)
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.
After the enumeration ends, return the answer.
The time complexity is O(n × log n), and the space complexity is O(log n). Here, n is the length of the array nums.
class Solution: def twoSumLessThanK(self, nums: List[int], k: int) -> int: nums.sort() i, j = 0, len(nums) - 1 ans = -1 while i < j: if (s := nums[i] + nums[j]) < k: ans = max(ans, s) i += 1 else: j -= 1 return ans(code-box)
