两数之和 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- 仅存在一个有效答案
代码结果
运行时间: 40 ms, 内存: 15.3 MB
/*
* 思路：
* 使用Java Stream API的方法来解决这个问题。我们可以将numbers数组与其索引一起流式处理，
* 以查找符合条件的两个数。
*/
import java.util.stream.IntStream;
public int[] twoSum(int[] numbers, int target) {
return IntStream.range(0, numbers.length)
.boxed()
.flatMap(i -> IntStream.range(i + 1, numbers.length)
.filter(j -> numbers[i] + numbers[j] == target)
.mapToObj(j -> new int[] {i + 1, j + 1}))
.findFirst()
.orElse(new int[] {-1, -1}); // 保证有唯一解
}解释
方法:
这个题解使用双指针的方法在有序数组中查找两数之和等于目标值的一对数字。初始时左指针 lo 指向数组开头，右指针 hi 指向数组结尾。每次计算两个指针对应元素之和 s，如果 s 小于目标值，说明需要增大 lo 以获得更大的值；如果 s 大于目标值，说明需要减小 hi 以获得更小的值；如果 s 等于目标值，则找到了符合条件的一对数，返回它们的下标即可。在移动指针时，还跳过了重复的元素以优化效率。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确保在跳过重复元素时，指针不会越过数组的边界，从而导致程序出错？
▷🦆
在题解中提到的跳过重复元素的步骤是否可能导致错过某些潜在的正确答案，特别是在数组中存在多个重复元素时？
▷🦆
为什么在找到和等于目标值时，直接返回下标而不再检查其他可能的组合？
▷🦆
在实现双指针算法时，如果数组中所有元素相加的总和都不等于目标值，算法是如何终止的？
▷相关问题
两数之和
给定一个整数数组 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) 的算法吗？
