英文网站建设解决方案,微信网站界面,网站开发费税率,多用户商城系统价格目录
1.定长滑动窗口
1.1 几乎唯一子数组的最大和(使用map来计数)
1.2 长度为k子数组中的最大和
2.不定长滑动窗口
2.1 最多k个重复元素的最长子数组
2.2 绝对差不超过限制的最长连续子数组(multiset#xff09;
2.3 将x减到0的最小操作数(正难则反 逆向思维)
2.4 统计…目录
1.定长滑动窗口
1.1 几乎唯一子数组的最大和(使用map来计数)
1.2 长度为k子数组中的最大和
2.不定长滑动窗口
2.1 最多k个重复元素的最长子数组
2.2 绝对差不超过限制的最长连续子数组(multiset
2.3 将x减到0的最小操作数(正难则反 逆向思维)
2.4 统计最大元素出现至少k次的子数组
2.5 乘积小于k的子数组 1.定长滑动窗口
1.1 几乎唯一子数组的最大和(使用map来计数)
class Solution {
public:long long maxSum(vectorint nums, int m, int k) {long long ans 0, sum 0;unordered_mapint, intcnt; //如何把重复的数字算成一个数字就要用到数组来进行计数了重复的数字对应的值大于1for (int i 0; i k - 1; i) //先求前k-1个数{sum nums[i];cnt[nums[i]];}for (int i k - 1; i nums.size(); i) //进去一个出来一个满足k个数{sum nums[i];cnt[nums[i]];if (cnt.size() m) //判断是否有m个不相同的数ans max(ans, sum);int out nums[i - k 1];sum - out;if (--cnt[out] 0) //如果只出现1次可以直接删除cnt.erase(out);}return ans;}
}; 这道题让我们求最大的问题而且是连续非空的子数组很容易想到滑动窗口但滑动窗口有定长和不定长两种题中说长度为k说明是定长的要求长度为k的几乎唯一子数组的最大和我们可以先求前k-1个数这样之后进来一个出去一个始终是k个数题目要求该子数组至少有m个不相同的数我们怎么记录是否有m个不相同的数呢我们可以用map来记录有几个不相同的数同时记录每个数字出现了几次如果某个子数组有m个不相同的数就更新答案之后就要出去一个数如果出去的这个数只出现了1次就要直接从map中删除。最后返回答案
1.2 长度为k子数组中的最大和
class Solution {
public:long long maximumSubarraySum(vectorint nums, int k) {unordered_mapint, int mp;long long res 0, sum 0;for (int i 0; i k - 1; i) {sum nums[i];mp[nums[i]];}for (int i k - 1; i nums.size(); i) {sum nums[i];mp[nums[i]];if (mp.size() k ) res max(res,sum);//这个已经去重了只要当mp的大小等于k时才会更新res的大小否则说明有重复数字不更新int x nums[i - k 1];if (--mp[x] 0) mp.erase(x);//及时清除为0的数字sum - x;}return res;}
}; 这道题也是定长滑动窗口要求子数组长度为k且元素各不相同和上一道题很相似也要用map值得注意的是什么时候我们更新答案只有当map中的元素个数等于k时说明子数组长度为k且元素各不相同这时候更新答案其他都是不断滑动的过程。
2.不定长滑动窗口
2.1 最多k个重复元素的最长子数组
class Solution {
public:int maxSubarrayLength(vectorint nums, int k) {unordered_mapint,intcnt;int ans0,l0;for(int r0;rnums.size();r){cnt[nums[r]];while(cnt[nums[r]]k)//如果有元素的出现频率大于k,就要不断左移左指针,直到这个元素的出现频率小于等于k,如果这个元素cnt[nums[l]]--;ansmax(ans,r-l1);}return ans;}
}; 这个没有规定长度要求满足条件的最长子数组很明显是不定长滑动窗口的问题。最多k个重复元素说明我们要记录元素出现了几次一旦超过了k次我们就要开始滑动直到子数组没有一个元素的出现频率大于k否则不断更新答案。
2.2 绝对差不超过限制的最长连续子数组(multiset
class Solution {
public:int longestSubarray(vectorint nums, int limit) {multisetintst;//关键在于找每个区间的最大值和最小值如果遍历寻找就会超时所以要找到一个合适的数据结结构//我们知道set/multiset/map是有序的set会去重所以我们使用multisetint l0;int res0;for(int r0;rnums.size();r){st.insert(nums[r]);while(*st.rbegin()-*st.begin()limit){st.erase(st.find(nums[l]));l;}resmax(res,r-l1);}return res;}
}; 这道题的关键在于求每个区间的最大值和最小值首先我们要把元素放到multiset中它不仅不会去重而且是有序的改变顺序并不影响答案这样我们使用两个迭代器rbegin()、begin()分别求逆序第一个元素和正序第一个元素两者之差就是绝对差如果大于限制我们就不断滑动窗口直到绝对值小于等于限制更新答案。
2.3 将x减到0的最小操作数(正难则反 逆向思维)
class Solution {
public:int minOperations(vectorint nums, int x) { //正难则反 逆向思维int target accumulate(nums.begin(), nums.end(), 0) - x;if (target 0) return -1;int ans -1, l 0, sum 0, n nums.size();for (int r 0; r n; r) {sum nums[r];while (sum target) sum - nums[l]; if (sum target) ans max(ans, r - l 1);}return ans 0 ? -1 : n - ans;}
}; 这道题借用灵神的思路正难则反逆向思维我们如果维护两个窗口的和使得和等于x肯定是很麻烦的那不如我们只维护一个窗口这个窗口的和要等于整数数组nums的和sum-x这样只用维护一个区间不得不说这个思维太帅了。accumulate函数是用来求某个区间元素的和0为初始值。
2.4 统计最大元素出现至少k次的子数组 class Solution {
public:long long countSubarrays(vectorint nums, int k) {long long ans0;int mx*max_element(nums.begin(),nums.end());int cnt0,left0; for(auto x:nums){if(xmx)cnt;while(cntk){if(nums[left]mx){cnt--;}left;}ansleft;}return ans;}
}; 这道题我们首先用max_element函数找出数组最大值然后就对最大值出现的次数进行计数如果子数组中最大值出现的次数等于k那么我们就要滑动寻找下一个满足条件的子数组如果左端点对应的值等于最大值cnt--左端点向右移动直到cnt!k此时更新答案left为什么要加left因为left是cntk进入循环向右移动left直到cnt!k退出循环得到了之前的子数组全部满足要求所以直接加left。
2.5 乘积小于k的子数组 class Solution {
public:int numSubarrayProductLessThanK(vectorint nums, int k) {if(k1)return 0;int ans0,mul1,l0;for(int r0;rnums.size();r){mul*nums[r];while(mulk){mul/nums[l];l;}ansr-l1;}return ans;}
}; 这道题和上一道题很类似如果[lr]区间内子数组的乘积小于k,那么[l1r][l2r]...[rr]全部小于k个数为r-l1更新答案每次加上r-l1即可。
