LeetCode 的 C++ 实现（八）两数之和

之和"/>

LeetCode 的 C++ 实现（八）两数之和

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力解法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;int length = nums.size();for(int i = 0 ;i < length ;i++){for(int j = 0; j <length && j != i;j++){if(nums[i] + nums[j] == target){result.push_back(i);result.push_back(j);return result;}}       }        return result;}
};

哈希表

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;map<int ,int> Cache;int length = nums.size();for(int i = 0 ;i < length ;i++)Cache.insert(map<int,int>::value_type(nums[i],i));     for(int j = 0; j< length ;j++)if(Cache.count(target - nums[j]) > 0 && Cache[target - nums[j]] != j){result.push_back(j);result.push_back(Cache[target- nums[j]]);return result;}  return result;}
};

改进的哈希表

思路：只进行一轮遍历，一边往哈希表里放，一边检查，如果有结果就直接返回

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;map<int ,int> Cache;int length = nums.size();    for(int j = 0; j< length ;j++){if(Cache.count(target - nums[j]) > 0){result.push_back(j);result.push_back(Cache[target- nums[j]]);return result;} Cache.insert(map<int,int>::value_type(nums[j],j)); }      return result;}
};