c 做网站,广东小程序系统开发,深圳企业专业网站建设,快速建站费用1.560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 示例 1#xff1a; 输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a; 输入#…1.560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 示例 1 输入nums [1,1,1], k 2
输出2示例 2 输入nums [1,2,3], k 3
输出2提示 1 nums.length 2 * 10^4-1000 nums[i] 1000-10^7 k 10^7 思路
数据规模也蛮大思考是不是用滑动窗口因为是子串不允许排序,所以用滑动窗口不断往后移暴力枚举遍历。 代码
暴力没成功当个反面例子我先贴一会
class Solution(object):def subarraySum(self, nums, k):i,k0,0count0for i in range(len(nums)):for j in range(i,len(nums)):if sum(nums[i:j])k : print(i,j)print(sum(nums[i:j]))count1return count
换个思路
使用前缀和的方法可以解决这个问题因为我们需要找到和为k的连续子数组的个数。通过计算前缀和我们可以将问题转化为求解两个前缀和之差等于k的情况。
假设数组的前缀和数组为prefixSum其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和ji j如果prefixSum[j] - prefixSum[i] k即从第i个位置到第j个位置的元素之和等于k那么说明从第i1个位置到第j个位置的连续子数组的和为k。
通过遍历数组计算每个位置的前缀和并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中我们检查是否存在prefixSum[j] - k的前缀和如果存在说明从某个位置到当前位置的连续子数组的和为k我们将对应的次数累加到结果中。
这样通过遍历一次数组我们可以统计出和为k的连续子数组的个数并且时间复杂度为O(n)其中n为数组的长度。
每次的前缀和放入map哈希表中哈希表的索引是pre如果未出现过则创建一个键值对。
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int mp;mp[0] 1;int count 0, pre 0;for (auto x:nums) {pre x;if (mp.find(pre - k) ! mp.end()) {count mp[pre - k];}mp[pre];}return count;}
};2.239. 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。 示例 1 输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2 输入nums [1], k 1
输出[1]提示 1 nums.length 10^5-10^4 nums[i] 10^41 k nums.length 思路
1)先是暴力解法就可以按照遍历的方式从头到尾以k为长度然后寻找最大值放入答案的列表中。
2)稍微优化一点点首先将前k个元素排序然后进行遍历。遍历过程中需要判断 是否大于最大值如果是则作为队首元素队尾出队如果小于最小值则直接舍弃如果处于中间则队尾元素出队该元素入队结束后重新排序写到这自己都觉得蠢了这叫优化
3使用双项队列。这里为了效率和快捷使用了 deque 容器也可以使用 list 容器。
声明了一个变量 dequeintwindow用于存储下标。这个变量有以下 特点:
①变量的最前端也就是 window.front()是此次遍历的最大值的下标 ②当我们遇到新的数时将新的数和双项队列的末尾也就是window.back()比较如果末尾比新数小则把末尾扔掉直到该队列的末尾比新数大或者队列为空的时候才停止做法有点像使用栈进行括号匹配。 ③双项队列中的所有值都要在窗口范围内 特点一只是方便我们获取每次窗口滑动一格之后的最大值我们可以直接通过 window.front() 获得。通过特点二可以保证队列里的元素是从头到尾降序的由于队列里只有窗口内的数所以他们其实就是窗口内第一大第二大第三大... 的数。特点三就是根据题意设置的。但我们实际上只用比较现在的下标和 window.front() 就可以了为什么呢 因为只要窗口内第一大元素也就是这个 window.front() 在窗口内那我们可以不用管第二大第三大元素在不在区间内了。因为答案一定是这个第一大元素。如果 window.front() 不在窗口内则将其弹出第二个大元素变成第一大元素第三大元素变成第二大元素以此类推。
代码编写的过程还要时刻检查队列是否为空防止抛出异常根据上面这些信息我们就可以编写此题的代码了。
代码
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {if(k0)return {};vectorintres;dequesize_twindow;/*Init K integers in the list*/for (size_t i 0; i k; i) {while (!window.empty() nums[i] nums[window.back()]) {window.pop_back();}window.push_back(i);}res.push_back(nums[window.front()]);/*End of initialization*/for (size_t i k; i nums.size(); i) {if (!window.empty() window.front() i - k) {window.pop_front();}while (!window.empty() nums[i] nums[window.back()]) {window.pop_back();}window.push_back(i);res.push_back(nums[window.front()]);}return res;}
};3.76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。 注意 对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。 示例 1 输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2 输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3: 输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。 提示 m s.lengthn t.length1 m, n 10^5s 和 t 由英文字母组成 思路
这个不会直奔题解
双指针我们移动右指针同时统计可以匹配目标字符串的字符个数当一个右指针可以匹配所有的目标字串时我们更新左端点找到一个最短的子串。
代码
class Solution {
public:string minWindow(string s, string t) {int n s.size(), m t.size();vectorint res(2, INT_MAX);unordered_mapchar, int h;unordered_mapchar, int hs;for(auto e : t) hs[e];int cnt 0;for(int i 0, j 0; i n; i){h[s[i]];if(hs.find(s[i]) ! hs.end()){if(h[s[i]] hs[s[i]]) cnt; // 统计当前s中可以匹配t的字符个数}while(cnt hs.size()) // 可以匹配所有字符时说明我们找到了一个合法子串{// 尝试更新左端点找到一个最短的子串h[s[j]]--;if(hs.find(s[j]) ! hs.end()){if(h[s[j]] hs[s[j]]) // 左端点的字符更新后如果无法满足和t匹配更新答案和种类数{cnt--;if(i - j 1 res[0]){res[0] i - j 1;res[1] j;}}}j;}}if(res[0] INT_MAX) return ; // 无法匹配当前的t字符串return s.substr(res[1], res[0]);}
};
