leetCode题号：1，两数之和：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
思路：①暴力deal法：就是遍历每一个nums数组的元素，然后对于每一轮的这个元素，分别往后去拿一个元素做加法 看是否 == target。一旦找到满足这个条件的两个元素（也就把下标i和j都返回即可）
代码：
class Solution {
public:
vector twoSum(vector& nums, int target) {
//vector tempVec;
int numsSize = nums.size();
for(int i = 0;i < numsSize -1;i++)
{
for(int j = i+1;j < numsSize;j++)
{
if((nums[i] + nums[j]) == target)
{
// tempVec.push_back(i);
// tempVec.push_back(j);
return {i,j};
}
}
}
return {};
}
};
运行结果：
②用哈希表map在遍历数组的元素时就把每个元素都push进去map中，然后再下一轮遍历数组的元素时就判断哈希表map中是否含有target - nums[i] 的值，若存在，也即找到满足 nums[i]+nums[j] ==target的i和j了，当然这里并不存在j这个下标，这里只是为了好说这么叙述而已！，这样就可以不用O(n^2)的时间复杂度来deal了，用O(n)即可deal这个问题了！
代码：
class Solution {
public:
vector twoSum(vector& nums, int target) {
map mp;
vector vec;// (2, -1);//预留2个空间，且对应的值为-1
vec.reserve(2);
int numsSize = nums.size();
for (int i = 0; i < numsSize; i++)
{
if (mp.count(target - nums[i]) > 0)//找到2个数的和 == target了！
{
int t1 = mp[target - nums[i]];
vec.push_back(t1);
cout <<"vec[0]:"<< vec[0] << endl;
int t2 = i;
vec.push_back(i);
cout << "vec[1]:" << vec[1] << endl;
break;
}
mp[nums[i]] = i;
//mp.insert({ nums[i],i });
}
return vec;
}
};
运行结果：
so，很明显地，用哈希表可以节省大量的遍历对比的操作！从而节省了大量的时间！！！
leetCode题号：350，两数之交集(二)：
给定两个数组，编写一个函数来计算它们的交集。
提示说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
- 我们可以不考虑输出结果的顺序。
思路：
①暴力deal法(其实还是用了哈希表map)：用2个map分别存储数组nums1和nums2中的元素以及其在map中所出现的次数。然后对于nums2数组而言，只要其每一轮的元素出现在了nums1所对应的map中时，此时求解这个元素在nums1和nums2中出现的次数（用一个迭代器it1->second it2->second即可拿到这个数字！），然后按照这个次数对应的插入到result数组中即可！
请看以下代码：
class Solution {
private:
typedef map::iterator mpIt;
map vectorTwoMap(vector& nums)
//这个函数负责将2个数组的元素以及其出现的次数对应为（弄成）哈希表map
{
map mp;
for (int i = 0; i < nums.size(); i++) {
//0代表没有存在过这种元素
int tempCnts = 0;
if (!mp.count(nums[i])) {
tempCnts++;
mp[nums[i]] = tempCnts;
}
else {
++mp[nums[i]];//相当于把it->second ++了！
}
}
return mp;
}
public:
vector intersect(vector& nums1, vector& nums2) {
map mp,mp2;
vector newVec;
int MinSize = min(nums1.size(), nums2.size());
newVec.reserve(MinSize);
mp = vectorTwoMap(nums1);
mp2 = vectorTwoMap(nums2);
for (mpIt it2 = mp2.begin(); it2 != mp2.end();it2++) {
mpIt it1 = mp.find(it2->first);
if (it1 != mp.end()) {
int minCnts = min(it2->second, it1->second);
while (minCnts) {
newVec.push_back(it2->first);
minCnts--;
}
}
}
return newVec;
}
};
运行结果：
从中我们可以看出来，这个暴力解决算法的空间复杂度非常高，不尽如人意！ 因此下面看了官方的解析之后我写出了第二种算法
②哈希表map法（用一个哈希表map即可deal问题了）：
用一个哈希表map来存储nums1和nums2中数组长度较小的那个数组的元素以及其在此数组中所出现的次数！为的就是节省空间！（你当然可以随便让数组1or数组2的元素插入map中，当然如果某个数组长度过大的话do插入操作实在了太耗时了，因此不这么干就是为了节省时间也节省哈希表所占用的空间）
再对长度较大的那个数组do一次遍历，每一次的遍历都判断其是否出现在（用mp.count(x)来判断）长度较小的那个数组中，若出现了，再判断其出现次数是否减减到0 了，若不是就把这个元素push进result数组中去，再继续对下一轮的元素的判别，这样就可以
自动地满足这个条件：让重复元素出现在result数组中的个数==在2个数组中的出现的最小次数
请看以下代码：
（若后期你coding时看不懂时可以自己画个图举几个小例子理解一下就很容易搞懂了！）
class Solution {
public:
vector intersect(vector& nums1, vector& nums2) {
map mp;
int minSize = min(nums1.size(), nums2.size());
if (nums1.size() > nums2.size()) {
return intersect(nums2, nums1);
}
vector insertion;
insertion.reserve(minSize);
for (int num : nums1)
{
int t = 0;
if (!mp.count(num)) {
t++;
mp.insert({ num ,t });
}
else {
mp[num] = mp[num] + 1;
}
}//把数组长度较小的那个数组的元素以及其咋map中出现的次数放入map中！
for (int j = 0; j < nums2.size(); j++)
{
if( mp.count(nums2[j]) && mp[nums2[j]] != 0)
{
insertion.push_back(nums2[j]);
mp[nums2[j]]--;
}
}
return insertion;
}
};
运行结果：
从结果我们可以看出来空间复杂度没有刚才那么高了！这是良好的！
