原意多读者的条目跳蛋 户外，从这篇著作起咱们运行一个新的系列：数据结构与算法，蓝本的计较机底层场所也会陆续更新。

谣言少说，运行今天的题目，这是数据结构与算法之LeetCode刷题系列第1篇。

今天的题目是两数之和，题目是这么的：

给定一个整数数组与一个target，在数组中找到两个数，其和等于target，并复返这两个数字的下标。示例：数组 nums = [2，7，11，15]， target = 9，则输出[0，1]，因为nums[0] + nums[1] == 9

题目不难，处罚步伐也有许多种，咱们顺次来看一下，任何题目都不错从最浅易的步伐运行去想，以下代码均为C++。

暴力解法

咱们领先固定一个数字，比如第一个数字2，然后遍历后头的元素，判断是否相加等于9，有就纪录下来，莫得则看下一个数字，也便是7，最终代码相配浅易，当时分复杂度为O(n^2)：

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

万万没猜想的是这么的代码的确不错AC（AC是刷题的常用术语，也便是Accept，通过代码的评测模范，包括正确性、耗时、内存的忽地等等）。

从这里的分析咱们其实不错知谈，这实质上其实是一个搜索问题，假如我知谈第一个数字是2，而target是9，那么咱们需要复兴“这个数组中是否有7这个数字”，因此这实质上是一个搜索问题。

既然是搜索问题，那么hash表明显是咱们最给力的火器。

hash 表

对于hash表后续会有专题详解。

C++中基于hash表这种数据结构的是std::unordered_map，咱们的念念路也很浅易，把扫数的数组元素看成key，数组下标看成值，因为题目条目咱们复返下标，因此这里必须把下标也存储起来，有了这么的map，剩下的就浅易了。

顺次遍历数组中每个元素N，查找target-N是否存在于map中即可。

vector<int> twoSum(vector<int>& nums， int target) { unordered_map<int， int> map; vector<int> res; for (int i = 0; i < nums.size(); i++) { auto iter = map.find(target - nums[i]); if (iter == map.end()) { map[nums[i]] = i; } else { res.push_back(i); res.push_back(iter->second); } } return res;}

明显，该算法时分复杂度是O(n)，因为一般情况下不错认为hash表能常数复杂度下查找到元素。

Hongkongdoll nude

是不是以为很浅易，详确，这里使用了map容器，那要是口试官条目你不得借助这种照旧写的库该如何办呢？

咱们在著作发轫分析过，这其实实质上是一个搜索问题，既然是搜索问题，那么处罚该问题的另一种念念路便是排序。

惟有排好序剩下的就浅易了，二分查找自然便是有序搜索问题的好赞理。

因此接下来的念念路便是排序加二分查找。

排序加二分查找

念念路照旧先容收场，接下来咱们手写快排，然而咱们排谁呢？

详确题目条目复返元素下标，因此排序时需要除了数组元素也需要把下标带上。

void quick_sort(vector<pair<int，int>>& nums， int b， int e) { if (b > e) return; int i = b - 1; for (int k = b; k < e; k++) { if (nums[k].second < nums[e].second) { swap(nums[++i]， nums[k]); } } swap(nums[++i]， nums[e]); quick_sort(nums， b， i - 1); quick_sort(nums， i + 1， e);}

有的同学可能莫得看懂这里的排序步伐，以致认为快排之类的排序算法只可靠死记硬背，其实不是的，这类经典的排序算法背后都有极其谬误的算法念念想，比如快排背后的念念想其实是divide and conquer，这是另一个稠密的话题，限于篇幅，咱们会在后续专题详解。

当今快排有了，接下来达成二分查找：

int binary_search(vector<pair<int，int>>& nums， int b， int e， int target) { while(b <= e) { int m = (b + e) / 2; if (nums[m].second == target) { return nums[m].first; } else if (nums[m].second < target) { b = m + 1; } else { e = m - 1; } } return -1;}

二分查找是一个看起来极其容易但写起来却极其容易出错的算法，不信你不错碰荣幸，这里暂时还不缱绻详确教练二分，后续还会屡次遭逢这个算法，当咱们积贮了敷裕多的示例后将系统先容这里波及的快排与二分。

有了这些函数后就不错达成主要逻辑了：

vector<int> twoSum(vector<int>& nums， int target) { vector<int> res; vector<pair<int， int>> nums_index; int size = nums.size(); for (int i = 0; i < size; i++) { nums_index.push_back(pair<int， int>(i， nums[i])); } quick_sort(nums_index， 0， size - 1); for (int i = 0; i < size - 1; i++) { int r = binary_search(nums_index， i + 1， size - 1， target - nums_index[i].second); if (r != -1) { res.push_back(nums_index[i].first); res.push_back(r); } } return res;}

运行一下发现耗时1s傍边，诚然也不错AC，但不错看到运行速率其实是很慢的，照旧hash表这种解法速率最快。

不错看到，一皆题目其实有许多解法，这里波及到hash、快排与二分查找，后续咱们还会屡次见到这些步伐跳蛋 户外，而咱们在积贮敷裕多的示例后会系统性教练这些数据结构与算法。