第51天(中等题 数据结构)

打卡第五十一天
2道中等题

题目：

思路：前缀和+哈希表，同余定理

代码：

int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> cnt;  // 哈希表int ans = 0, s = 0;          // 答案计数、当前前缀和余数for(int x : nums){cnt[s]++;                // 当前余数的出现次数s = (s + x % k + k) % k; // 更新余数（+k处理负数情况）ans += cnt[s];           // 计数}return ans;
}

题目：

思路：

代码：

long long beautifulSubarrays(vector<int>& nums) {unordered_map<int,int> cnt;  // 哈希表int mask = 0;                // 当前前缀异或值long long ans = 0;cnt[0] = 1;                  // 初始化空子数组的异或为0for(int x : nums){mask ^= x;               // 更新前缀异或值ans += cnt[mask]++;      // 加上之前出现相同值的次数，当前值出现次数+1}return ans;
}

耗时≈一小时 明天继续