本文主要是介绍力扣930.和相同的二元子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣930.和相同的二元子数组
哈希表法
-
最终[l,r]区间和为goal
-
sum为记录的非递减前缀和
- sum[r] - sum[l] = goal
- 因此遍历右端点时 找到左端点为sum[l]的出现次数即可
-
class Solution {public:int numSubarraysWithSum(vector<int>& nums, int goal) {int n = nums.size();unordered_map<int,int> cnt;int res=0,sum=0;for(auto num:nums){cnt[sum] ++;sum += num;res += cnt[sum - goal];}return res;}};
多指针法
-
用l1,l2存符合要求的l的区间
-
class Solution {public:int numSubarraysWithSum(vector<int>& nums, int goal) {int n = nums.size();int res=0,s1=0,s2=0;for(int l1=0,l2=0,r=0;r<n;r++){s1 += nums[r];s2 += nums[r];//s1 --> goalwhile(l1 <= r && s1 > goal) s1 -= nums[l1++];//s2 --> <goalwhile(l2 <= r && s2 >= goal) s2 -= nums[l2++];res += l2 - l1;}return res;}};
这篇关于力扣930.和相同的二元子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!