两数之和
暴力法
两层for循环，遍历数组求满足target的值
复杂度高
哈希表
遍历一次数组，查看当前遍历的数组的值时候，map里面有无target - nums[i]。
- 如果没有，将当前遍历的数和下标组成pair存入map中。
- 如果有，返回当前遍历数组值下标和map中找的的值下标。
#include <iostream> #include<vector> #include <unordered_map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> num_map; for (int i = 0; i < nums.size(); i++) { auto iter = num_map.find(target - nums[i]); if (iter == num_map.end()) { num_map.insert(pair<int, int>(nums[i], i)); } else { return { (*iter).second , i}; } } } }; int main() { vector<int>nums = { 2,7,11,15 }; int target = 9; Solution a; vector<int>result = a.twoSum(nums , target); for (int i = 0; i < result.size(); i++) { cout << result[i] << ' '; } return 0; }
二刷
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int ,int> my_map; for(int i=0 ; i<nums.size() ;i++) { auto it = my_map.find(target - nums[i]); if( it != my_map.end()) return {it->second,i}; else my_map.insert(pair<int,int>(nums[i],i)); } return {}; } };
高频题
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int left , right; for(left = 0 ; left < nums.size() ;left++) { for(right = left + 1 ; right < nums.size() ; right++) { if( nums[right] + nums[left] == target ) return {left,right}; } } return {}; } };
