小于 K 的两数之和
难度:
标签:
题目描述
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/* 使用Java Stream的题解代码和注释 */
import java.util.Arrays;
public class TwoSumLessThanKStream {
public int twoSumLessThanK(int[] A, int K) {
// 使用流排序数组
Arrays.sort(A);
// 定义变量记录最大和
int maxSum = -1;
// 使用双指针法遍历数组
int left = 0, right = A.length - 1;
while (left < right) {
// 计算两数之和
int sum = A[left] + A[right];
// 如果和小于K
if (sum < K) {
// 更新最大和
maxSum = Math.max(maxSum, sum);
// 移动左指针以增加sum
left++;
} else {
// 否则, 移动右指针以减少sum
right--;
}
}
// 返回结果
return maxSum;
}
}
解释
方法:
该题解采用双指针方法。首先对数组进行排序，然后使用两个指针分别指向数组的起始位置和结束位置。在遍历过程中，计算两个指针指向的元素之和，如果和小于k，则更新答案，并将左指针向右移动一位；如果和大于等于k，则将右指针向左移动一位。这样可以在保证和小于k的前提下，尽可能地让和大，直到两个指针相遇为止。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在和小于k的条件下选择将左指针向右移动而不是右指针向左移动？这样做的目的是什么？
▷🦆
在实现双指针策略时，如何确保在移动指针后，仍然能够维持和小于k的最大值？
▷🦆
如果数组中存在相同的元素值，这种双指针方法是否会受到影响？例如，相同元素值如何影响最终的答案计算？
▷🦆
题解中的算法在处理极端情况，如最小或最大整数值的数组时，是否有可能出现整数溢出？如果有，如何避免？
▷相关问题
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
乘积小于 K 的子数组
给你一个整数数组
nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
示例 2：
输入：nums = [1,2,3], k = 0 输出：0
提示:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106