一、 刷题选做什么准备吗？
- 准备一个白纸/打开 vscode
- 断网
- 25 分钟倒计时
二、题目要求
别说题目简单，
这个才刚刚开始，上来不需要难度太大的题目。
要求
- 空间复杂度 O(1)
- 时间复杂度 O(n)
- 返回值按题目要求，需要 +1，表示从 1 开始的下标
反问
三、思路：采用什么数据结构与算法
| 方法 |
时间复杂度 |
空间复杂度 |
是否适用本题 |
是否能处理重复值 |
| 暴力双层循环 |
O(n²) |
O(1) |
✅（但慢） |
✅ |
| 哈希表 + 一遍扫描 |
O(n) |
O(n) |
❌（违背空间要求） |
✅ |
| 排序 + 双指针 |
O(n) |
O(1) ✅ |
✅ |
✅ |
四、代码实现
c++版本
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target)
{
int begin = 0 ;
int end = numbers.size() -1 ; //heap-buffer-overflow
while (begin < end) {
int cur_target = numbers[begin] + numbers[end];
if (cur_target >target) {
end --;
} else if ( cur_target < target) {
begin++;
} else if (cur_target == target) {
//如果重复的值，
return {begin+1,end +1};
}
}
return {-1,-1};
}
};
|
Rust版本(不支持重复元素)
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
//数据结构：定义双指针遍历
let mut left = 0; //变量默认是不可变（immutalbe）
let mut right = numbers.len() -1;
//算描述 :循环变量
loop
{
if left >=right {
return vec![-1,-1];
}
let cur_target = numbers[left] + numbers[right];
if cur_target > target {
right -=1;
} else if cur_target < target {
left +=1;
} else {
return vec![left as i32 +1,right as i32 +1];
}
}
}
}
|
参考
您的点赞，转发 将是我最大的写作动力！
如果更多疑问，欢迎留言评论。
次阅读