深圳市罗湖网站建设,如何做一个网站的功能吗,北京网站建设公司华网制作作,云南网站建设公司排名先上题目 题目链接#xff1a;题目链接
这题我最先想到的就是前缀和a#xff0c;构造好了以后就遍历每一个[l,r]数组#xff08;满足题目要求的连续区间数组#xff09;#xff0c;奈何倒数第二个样例时间超限 先给出原思路代码
class Solution {
public:int subarray…先上题目 题目链接题目链接
这题我最先想到的就是前缀和a构造好了以后就遍历每一个[l,r]数组满足题目要求的连续区间数组奈何倒数第二个样例时间超限 先给出原思路代码
class Solution {
public:int subarraySum(vectorint nums, int k) {//vectorint 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功能都是查找函数实现On一次遍历全部数字就好了代码如下已ac主要是把上面那份代码的“核心需要优化的部分”修改
class Solution {
public:int subarraySum(vectorint nums, int k) {//vectorint 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_mapint,int myMap;// 核心需要优化的地方for (int i 0; i len; i) {//目的是a[i]-a[l]k 所以要寻找a[l]if(myMap.count(a[i]-k)) xmyMap[a[i]-k];myMap[a[i]];}return x;}
};这个思路让我想起之前做过一道题几乎完全一样的思路利用哈希表 题目链接 实现代码
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int myMap;vectorint x;for(int i0;inums.size();i){//说明first是具体数值auto itmyMap.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进行查找与操作大家可以根据这两道题找找思路以后碰到类似题考虑该方法~
