class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
}
};
1099. 小于 K 的两数之和
给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。
示例 1：
输入：nums = [34,23,1,24,75,33,54,8], k = 60 输出：58 解释： 34 和 24 相加得到 58，58 小于 60，满足题意。
示例 2：
输入：nums = [10,20,30], k = 15 输出：-1 解释： 我们无法找到和小于 15 的两个元素。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 10001 <= k <= 2000原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2023-10-15 19:05:25
func twoSumLessThanK(A []int, K int) int {
res := make([]int, 0)
start, end := 0, 0
for i := range A {
start = i
end = len(A) - 1
for {
if end == start {
break
}
if A[start]+A[end] < K {
res = append(res, A[start]+A[end])
}
end--
}
}
sort.Ints(res)
if len(res) == 0 {
return -1
}
return res[len(res)-1]
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-15 19:04:58
class Solution:
def twoSumLessThanK1(self, nums: List[int], k: int) -> int:
answer = -1
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
sum = nums[i] + nums[j]
if sum < k:
answer = max(answer, sum)
return answer
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums.sort()
answer = -1
left = 0
right = len(nums) -1
while left < right:
sum = nums[left] + nums[right]
if (sum < k):
answer = max(answer, sum)
left += 1
else:
right -= 1
return answer
java 解法, 执行用时: 1 ms, 内存消耗: 39.4 MB, 提交时间: 2023-10-15 19:04:32
class Solution {
// 暴力
public int twoSumLessThanK1(int[] nums, int k) {
int answer = -1;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int sum = nums[i] + nums[j];
if (sum < k) {
answer = Math.max(answer, sum);
}
}
}
return answer;
}
// 双指针
public int twoSumLessThanK(int[] nums, int k) {
Arrays.sort(nums);
int answer = -1;
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < k) {
answer = Math.max(answer, sum);
left++;
} else {
right--;
}
}
return answer;
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 9.1 MB, 提交时间: 2023-10-15 19:03:47
class Solution {
public:
// 暴力
int twoSumLessThanK1(vector<int>& nums, int k) {
int answer = -1;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
int sum = nums[i] + nums[j];
if (sum < k) {
answer = max(answer, sum);
}
}
}
return answer;
}
// 双指针
int twoSumLessThanK(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int answer = -1;
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < k) {
answer = max(answer, sum);
left++;
} else {
right--;
}
}
return answer;
}
};