NC61 两数之和【牛客网】

零、原题链接

NC61 两数之和

一、题目描述

二、测试用例

三、解题思路

3.1 排序+双指针

1. 基本思路：
     先对序列进行排序，然后使用双指针从头和尾进行操作。
2. 具体思路：
   • 建立值到下标的映射；
   • 序列从小到大排序；
   • 定义双指针 i 和 j ，指针 i 表示头，指针 j 表示尾，迭代直到 i>j ：
     • 如果两个指针的值相加等于目标，则返回对应值在序列的位置；
     • 如果两个指针的值相加大于目标，则 j-- ；【想办法减小两个值的和】
     • 如果两个指针的值相加等于目标，则 i++ ；【想办法增加两个值的和】

3.1 散列

1. 基本思路：
     每次遍历到一个元素，从遍历过的数中看看是否能找到目标减去该元素的值。
2. 具体思路：
   • 遍历所有元素
   • 如果可以在 map 中找到目标值减去该元素的值，则返回两个元素的下标；
   • 如果没有找到，则将该元素按照 {元素值，下标} 的方式插入到 map 中；

四、参考代码

4.1 排序+双指针

时间复杂度：$\mathrm{O}(nlogn)$
空间复杂度：$\mathrm{O}(n)$

#include <functional>
#include <numeric>
#include <utility>
#include <vector>
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numbers int整型vector* @param target int整型* @return int整型vector*/vector<int> twoSum(vector<int>& numbers, int target) {int n = numbers.size();vector<pair<int, int>> numtoi(n);vector<int> ans;for (int i = 0; i < n; i++) {numtoi[i] = make_pair(numbers[i], i + 1);}sort(numtoi.begin(), numtoi.end(), [&](const pair<int, int>& x,const pair<int, int>& y) {return x.first < y.first;});int i = 0, j = n - 1;while (i < j) {if (numtoi[i].first + numtoi[j].first == target) {ans.emplace_back(numtoi[i].second);ans.emplace_back(numtoi[j].second);if (ans[0] > ans[1])swap(ans[0], ans[1]);break;} else if (numtoi[i].first + numtoi[j].first < target) {i++;} else {j--;}}return ans;}
};

4.2 散列

时间复杂度：$\mathrm{O}(n)$
空间复杂度：$\mathrm{O}(n)$

#include <functional>
#include <numeric>
#include <unordered_map>
#include <utility>
#include <vector>
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param numbers int整型vector* @param target int整型* @return int整型vector*/vector<int> twoSum(vector<int>& numbers, int target) {unordered_map<int, int> m;for (int i = 0; i < numbers.size(); i++) {int rest = target - numbers[i];if (m.count(rest) == 1) {return {m[rest] + 1, i + 1};} else {m.emplace(numbers[i], i);}}return {};}
};