[每日一题] 第十四题：和为s的两个数字
0 / 0 / 创建于 4年前
DRose 的个人博客
题目描述
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
题解
方法一：我的题解
因为是递增排序，我们就直接从数组两边遍历，定义一个 left 和 right，当两数之和小于 target时，说明要右移左边的数，当两数之和大于 target 时，说明要左移右边的数，当两数之和等于 target 时，输出结果。
注意：我的代码中没有判断如果不存在的情况，虽然通过了，但是是不对的，我没有改正，当做反例，下面的一个题解是正例。
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
int left = 0;
int right = nums.length - 1;
while ((nums[left] + nums[right]) != target) {
if ((nums[left] + nums[right]) < target) {
left ++;
} else {
right--;
}
}
result[0] = nums[left];
result[1] = nums[right];
return result;
}
}
复杂度分析
- 时间复杂度： 需要遍历整个数组，所以时间复杂度为 O(N)。
- 空间复杂度： 额外定义了两个变量
left和right，所以空间复杂度为 O(2)。
方法二：双指针法（和我的思路一致，更详细）
解题思路：
利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)；
注意本题的 nums 是 排序数组，因此可使用 双指针法 将空间复杂度降至 O(1)。
算法流程：
初始化： 双指针 i，j 分别指向数组 nums 的左右两端（俗称对撞双指针）。
循环搜索： 当双指针相遇时跳出：
- 计算和 s = nums[i] + nums[j];
- 若 s > target，则指针 j 向左移动，即执行 j = j - 1；
- 若 s < target，则指针 i 向右移动，即执行 i = i + 1；
- 若 s = target，立即返回数组 [nums[i], nums[j]]；
返回空数组，代表无和为 target 的数字组合。
正确性证明：
记每个状态为 S(i,j) ，即 S(i,j)=nums[i]+nums[j] 。假设 S(i,j)<target ，则执行 i=i+1 ，即状态切换至 S(i+1,j) 。
- 状态 S(i,j) 切换至 S(i+1,j) ，则会消去一行元素，相当于 消去了状态集合 {S(i,i+1),S(i,i+2),…,S(i,j−2),S(i,j−1),S(i,j) } 。（由于双指针都是向中间收缩，因此这些状态之后不可能再遇到）。
- 由于 nums 是排序数组，因此这些 消去的状态 都一定满足 S(i,j)<target ，即这些状态都 不是解 。
- 结论： 以上分析已证明 “每次指针 i 的移动操作，都不会导致解的丢失” ，即指针 i 的移动操作是 安全的 ；同理，对于指针 j 可得出同样推论；因此，此双指针法是正确的。
![[每日一题] 第十四题：和为s的两个数字](https://cdn.learnku.com/uploads/images/202007/31/61979/5VNX2tw8oO.png!large)
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}
复杂度分析
- 时间复杂度 O(N) ： N 为数组 nums 的长度；双指针共同线性遍历整个数组。
- 空间复杂度 O(1) ： 变量 i, j 使用常数大小的额外空间。
题解来源
作者：jyd
链接：leetcode-cn.com/problems/he-wei-sd...
来源：力扣（LeetCode）
来源
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/he-wei-sd...
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号