Two Sum

2019-11-06 09:30:29

字体：大中小

来源：转载

供稿：网友

★

class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { for (int j = 0; j < nums.size() - 1; j++) { for (int i = j + 1; i < nums.size(); i++) { if (nums[i] + nums[j] == target) { vector<int> index; index.push_back(i); index.push_back(j); return index; } } } }};使用双重循环，外层为第一个加数，循环由下标0到nums大小减一，里层为第二个加数，下标为外层加一到nums大小。新建一个vector保存返回值。当任意两个数值相加满足条件target时，存入vector。时间复杂度为O（n^2）.

★★★

class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int> hash_map; int tofind = 0; for (int i = 0; i < nums.size(); i++) { tofind = target - nums[i]; if (hash_map.find(tofind) != hash_map.end()) { vector<int> vec; vec.push_back(i); vec.push_back(hash_map[tofind]); return vec; } else { hash_map[num[i]] == i; } } }};新建一个名为hash_map的容器；声明tofind变量。新建一个vector类型的数组vec。使用单层循环，从下标0开始循环到i，并令tofind等于target与nums[i]之差。最初hash_map为空，在容器中寻找tofind。若存在，将i与hash_map存入vec中；若不存在，将i以下标num[i]存入hash_map。返回vec。时间复杂度为O（n）。

上一篇：cartographer开源代码的理解

下一篇：人啊. 就是不愿意承认自己的错误