剑指Offer.57-和为s的两个数字
剑指Offer.57-和为s的两个数字
题目链接
<剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode） (leetcode-cn.com)>
问题描述
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可
个人想法
线性扫描加二分查找
时间复杂度：$O(Nlog_2N)$
空间复杂度：$ O(1)$
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int[] twoSum(int[] nums, int target) {
int find = 0;
for(int i=0;i<nums.length;i++){
find = target-nums[i];
int left = 0;
int right = nums.length-1;
int mid = left + (right-left)/2;
while(left<=right){
if(nums[mid] == find){
return new int[]{nums[i],find};
}else if(nums[mid] > find){
right = mid-1;
mid = left + (right-left)/2;
}else{
left = mid + 1;
mid = left + (right-left)/2;
}
}
}
return new int[0];
}
}
|
官方解法
使用双指针同时从左右两次向中间进行扫描，若当前结果大于target右侧指针向左移动一个单位，若当前结果小于target左侧指针向右移动一个单位，当双指针相遇时跳出，若为扫描到，返回空数组
时间复杂度：$O(N)$
空间复杂度：$ O(1)$
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
| 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];
}
}
|
其他解法
使用哈希表存储扫描过的数据，每遍历一个元素，首先判断$target-nums[i]$是否在hash表中，若在表示有解，直接返回，若不在，将当前的值存储入hash表中
时间复杂度：$O(N)$
空间复杂度：$ O(N)$