lc167. 两数之和 ii - 输入有序数组

题目链接:167. 两数之和 II - 输入有序数组

题解

数组已经排好序,对于 numbers[i]numbers[i] 只需要用二分搜索查找 numbers 中有没有满足 targetnumbers[i]target - numbers[i]

另外也可以用双指针来做,复杂度可以降到 O(n)O(n)

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int>ans;
for (int i=0;i<numbers.size();i++) {
int need = target - numbers[i];
int k = lower_bound(numbers.begin()+i+1, numbers.end(), need) - numbers.begin();
// cout<<need<<" "<<k<<" "<<i<<endl;
if (k >= numbers.size()) {
continue;
}
if (numbers[i] + numbers[k] == target) {
ans.push_back(i+1);
ans.push_back(k+1);
break;
}
}
return ans;
}
};

lc167. 两数之和 ii - 输入有序数组

https://blog.xiang578.com/problem/lc167.html

作者

Ryen Xiang

发布于

2023-07-08

更新于

2024-08-05

许可协议


网络回响

评论