leetcode 第一题-两数之和的四种解法：

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [1 5 6 7 10 26], target = 15
输出：[1,4]

1.纯暴力解法：

这个没什么好说的，就是纯暴力遍历两遍：时间复杂度O(n²)空间复杂度O(1)

代码如下：

vector<int> twoSum(vector<int>& nums, int target) {
vector<int>
cnt;
int flag = 0;
for (int i = 0; i < nums.size(); i++){
for (int j = i + 1; j < nums.size(); j++){
if (nums[i] + nums[j] == target){
cnt.push_back(i);
cnt.push_back(j);
flag = 1;
break;
}
}
if (flag) break;
}
return cnt;
}

2.二分解法：

二分可以优化算法的时间复杂度，对于本题来说就是将第二个循环的时间复杂度降到logn级别，故整体为O(nlogn)，空间复杂度为O(1)。

值得一提的是二分的本质是通过比较删去没有答案的区间，故如果想要二分还需要进行排序，因为题目要求是无序的，然后再使用一个数组存储二分前每个数字的下标。

但是对于本题来说，如果新开一个数组存储每个元素的下标就相当得不偿失了，因为数据范围是10⁹需要维护如此长的数组。

故我们假设本题给出的数据是排序后的，给出相应代码：

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i = 0; i < nums.size(); i++){
int l = i + 1, r = num.size() - 1;
while (l <= r){
mid = (l + r) / 2;
if (nums[mid] == target - nums[i]){
ans.push_back(i);
ans.push_back(mid);
break;
} else if(nums[mid] < target - nums[i]){
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return ans;
}
};

3.双指针法：

在将双指针法之前我们需要引入一道题方便理解：

题目描述

给定一个 n 行 m 列的二维矩阵和一个目标数 t，二维矩阵中对于每一行从左到右不下降（右边的数大于等于左边的数），对于每一列从上到下不下降（下边的数大于等于上边的数）。现要在数组中找到目标数 t，并输出其所在位置的行数和列数。

输入

第一行两个整数 n,m。（1≤n,m≤3000）

接下来一个二维矩阵，矩阵内所有数均小于 200000。

最后一行一个整数 t。（1≤t≤200000）

输出

输出两个用空格隔开的数表示位置（从一开始计数），答案有唯一解。

样例输入

3 4
1 2 3 4
5 6 15 20
7 10 20 25
15

样例输出

2 3

数据规模与约定

时间限制：1 s

内存限制：256 M

100% 的数据保证 1≤n,m≤3000

对于这道题，可能很多人一看，这不直接双循环遍历找就完了呗，但对于本题，他给的二维矩阵是一个特殊的，有顺序你的矩阵，再遍历就有点浪费它的特殊性了，那我们可以看一下。

二维矩阵中对于每一行从左到右不下降（右边的数大于等于左边的数），对于每一列从上到下不下降（下边的数大于等于上边的数）。

这样我们就可以用两个指针一个横指针，一个纵指针移动来找其特定值。

比如我们现在需要找15这个值，我们不妨令初始指向左下，也就是指向7.

我们要找的值大于7，那么我就让我的横指针向右移，此时我便舍去了第0列。

指向10,15>7，继续右移横指针，舍去第1列。

20 > 15上移纵指针，指向15找到了，over。

双指针的有趣在于，一次可以舍去一行或者一列，故可以极大优化算法。

本题代码如下：

#include<iostream>
using namespace std;
int n, m, nums[3000][3000];
int main(){
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> nums[i][j];
}
}
int tar;
cin >> tar;
int x = n - 1, y = 0;
while (x > 0 && y < m ){
if (nums[x][y] == tar){
cout << x + 1 << " " << y + 1 <<endl;
return 0;
} else if (nums[x][y] < tar){
y++;
} else {
x--;
}
}
return 0;
}

而后对于本题：

仍旧是假定给的数据是有序的：

执行代码如下，实际上就是把一维的和展开为二维即可。

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
int l = 0 , r = nums.size() - 1;
while (l <= r){
if (nums[r] + nums[l] == target){
ans.push_back(l);
ans.push_back(r);
break;
} else if(nums[l] + nums[r] < target ){
l++;
} else {
r--;
}
}
return ans;
}
};

其时间复杂度为O(logn)

4.利用map容器

之前两周优化后的算法都是在有序情况下才有良好的表现，对于无序情况便需要费很大力气了。

但是map容器解决了这个问题，他包含着一种映射关系，我们就可以直接使得数字与下标相互映射即可。

对于本题而言，利用map或者unordered_map都可以，但是由于unordered_map在一些情况有着姣好的表现。为了加深映像，所以我们采用unordered_map

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> ans;
for (int i = 0; i < nums.size(); i++){
if (m.count(target - nums[i])){
ans.push_back(i);
ans.push_back(m[target - nums[i]]);
}
m[nums[i]] = i;
}
return ans;
}
};

这份代码写的就很有技巧性了

首先是它利用一个循环就完成了向map里面填充，和遍历求值得工作。

而这其中的两点在于没有定义unordered_mulitmap ， 因为定义mulit需要重载一个大于或者小于号，又浪费工作了。

而push_back(i)与push_back(m[target - nums[i]])就很好的避免了重复数的问题，i始终是大于m中元素映射的下标的，故没有了重复的障碍。

而map内部实现大部分是红黑数，其增删改查的时间复杂度是O(1)级别是最佳的优化了。但是由于外层循环的原因，故整体时间复杂度应该是O(n)

总结

对于四种方法，给出其时空复杂度的对比：

最后

以上就是外向心情为你收集整理的leetcode 第一题-两数之和的四种解法：leetcode 第一题-两数之和的四种解法：的全部内容，希望文章能够帮你解决leetcode 第一题-两数之和的四种解法：leetcode 第一题-两数之和的四种解法：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。