https://leetcode-cn.com/problems/two-sum/solution/
1、简单暴力法
class Solution { public: vector<int> twoSum(vector<int> &nums, int target); }; vector<int> Solution::twoSum(vector<int> &nums, int target) { vector<int> ans; for(int i = 0; i < nums.size()-1; i++) { for(int j = i; j < nums.size(); j++) { if(nums[i] + nums[j] == target) { ans.push_back(i); ans.push_back(j); return ans; } } } }
2、二次哈希法
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target);
};
vector<int> Solution::twoSum(vector<int> &nums, int target) {
vector<int> ans;
map<int,int> hmap;
for(int i = 0; i < nums.size(); i++) hmap[nums[i]] = i;
for(int i = 0; i < nums.size(); i++) {
int d = target - nums[i];
if(hmap.find(d) == true && hmap[d]] != i) {
ans.push_back(i);
ans.push_back(hmap[d]);
return ans;
}
}
}
遍历数组，
对每个元素进行考察时，
因为target已知，
所以将问题转化为（target-正在考察的元素）是否在数组里。
原文：https://www.cnblogs.com/huangming-zzz/p/10201470.html