如何妙用哈希表来优化遍历查找过程？刷题感悟总结，c++实现
先上题目
题目链接：题目链接
- 这题我最先想到的就是前缀和a，构造好了以后就遍历每一个[l,r]数组（满足题目要求的连续区间数组），奈何倒数第二个样例时间超限
- 先给出原思路代码
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//vector<int> a;int x = 0;int len = nums.size();a.resize(len + 2, 0);a[1] = nums[0];for (int i = 2; i <= len; i++) {a[i] = nums[i - 1]; // 0号赋值，a[i] += a[i - 1];}// 核心需要优化的地方for (int i = 0; i <= len; i++) {for (int j = i + 1; j <= len; j++) {if (a[j] - a[i] == k)x++;}}return x;}
};
- 但是介于给出的数组中可能有正数、负数，所以同样的前缀和大小可能有好几个，可以巧妙利用哈希表的find功能（或者count功能，都是查找函数），实现O（n）一次遍历全部数字就好了
- 代码如下，已ac，主要是把上面那份代码的“核心需要优化的部分”修改
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//vector<int> a;int x = 0;int len = nums.size();a.resize(len + 2, 0);a[1] = nums[0];//从a[1]开始存前缀和for (int i = 2; i <= len; i++) {a[i] = nums[i - 1]; // 0号赋值，a[i] += a[i - 1];}unordered_map<int,int> myMap;// 核心需要优化的地方for (int i = 0; i <= len; i++) {//目的是a[i]-a[l]==k 所以要寻找a[l]if(myMap.count(a[i]-k)) x+=myMap[a[i]-k];myMap[a[i]]++;}return x;}
};
- 这个思路让我想起之前做过一道题，几乎完全一样的思路，利用哈希表
题目链接
实现代码：
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> myMap;vector<int> x;for(int i=0;i<nums.size();i++){//说明first是具体数值auto it=myMap.find(target-nums[i]);if(it!=myMap.end()){x ={i,it->second};return x;}myMap[nums[i]]=i;}return x;}
};
- 共同点是它们都利用了哈希表（unordered_map）的特性来快速查找和存储信息，以便在遍历数组时可以高效地找到满足条件的元素或子数组。
- 两道题都是对vector& nums, int k进行查找与操作，大家可以根据这两道题找找思路，以后碰到类似题考虑该方法~