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
We can first sort the array
Next, we enumerate each element
After the enumeration ends, return the answer.
The time complexity is
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;
}
Similar to Solution 1, we can first sort the array
Next, we use two pointers
After the enumeration ends, return the answer.
The time complexity is
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
class Solution {
public int twoSumLessThanK(int[] nums, int k) {
Arrays.sort(nums);
int ans = -1;
for (int i = 0, j = nums.length - 1; i < j;) {
int s = nums[i] + nums[j];
if (s < k) {
ans = Math.max(ans, s);
++i;
} else {
--j;
}
}
return ans;
}
}
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ans = -1;
for (int i = 0, j = nums.size() - 1; i < j;) {
int s = nums[i] + nums[j];
if (s < k) {
ans = max(ans, s);
++i;
} else {
--j;
}
}
return ans;
}
};
func twoSumLessThanK(nums []int, k int) int {
sort.Ints(nums)
ans := -1
for i, j := 0, len(nums)-1; i < j; {
if s := nums[i] + nums[j]; s < k {
ans = max(ans, s)
i++
} else {
j--
}
}
return ans
}