力扣1248.统计优美子数组
力扣1248.统计优美子数组
- 同930.
哈希表法
-
求前缀和
-
class Solution {public:int numberOfSubarrays(vector<int>& nums, int k) {int n = nums.size();unordered_map<int,int> cnt;int res=0,sum=0;for(int i=0,j=0;i<n;i++){cnt[sum] ++;if(nums[i] & 1) sum ++;res += cnt[sum - k];}return res;}};
多指针法
-
用两个左指针卡左边可取的区间范围
-
class Solution {public:int numberOfSubarrays(vector<int>& nums, int k) {int n = nums.size();int res=0,s1=0,s2=0;for(int i=0,j1=0,j2=0;i<n;i++){int x = (nums[i] & 1);s1 += x;s2 += x;//s1 --> s1 < kwhile(j1 <= i && s1 >= k) s1 -= (nums[j1++] & 1);//s2 --> s2 == kwhile(j2 <= i && s2 > k) s2 -= (nums[j2++] & 1);//此时j1的位置比j2靠右res += j1 - j2;}return res;}};