国外比较有名的设计工作室网站百度站长统计

题目描述：

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

要求：

可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

解答：

方法一、暴力枚举：

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

方法二、哈希表:

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hashtable;for(int i=0;i<nums.size();++i){auto it=hashtable.find(target-nums[i]);if(it !=hashtable.end()){return{it->second,i};}hashtable[nums[i]]=i;}return {};}
};

哈希表的特性：

(1)查找时复杂度为O(1)；

(2)使用insert插入元素时，第一次insert成功，第二次insert不能将第一次的值覆盖；

(3)使用索引赋值时，能将元素进行有效更新。

例：

#include<unordered_map>// 初始 map 的内容为{{1，1}，{2，2},{3,3}}
unordered_map<int, int> map{{1,1},{2,2},{3,3}};
//修改第3个元素
map[3]=4;
// map的内容更新为{{1，1}，{2，2},{3,4}}
// 插入新元素
map.insert({4,10});
// map的内容更新为{{1，1}，{2，2},{3,4},{4,10}}
// 试图修改map第4个元素的值
map.insert({4,20});
// map的内容仍为{{1，1}，{2，2},{3,4},{4,10}}