930. Binary Subarrays With Sum

题解

这道题我之前确实没有思路。
只想到了用前缀和去求解，但是我认为前缀和求的方式是O(n^2)的算法。
这个地方包含了一层递推关系的。
goal = s[i] - s[j - 1]。对于一个固定的前缀和s[i]，我们期望判断之前有多少的前缀和是s[i] - goal。所以我们可以利用一个hash表，存储所有的s[j]。

代码

  1. class Solution {
  2. public:
  3.     int numSubarraysWithSum(vector<int>& nums, int goal) {
  4.         unordered_map<int, int> cnt;
  5.         int res = 0;
  6.         cnt[0] ++;
  7.         for (int i = 1, s = 0; i <= nums.size(); i ++) {
  8.             s += nums[i - 1];
  9.             // s[i] - s[j - 1] = goal
  10.             // s[j - 1] = s[i] - goal;
  11.             res += cnt[s - goal];
  12.             cnt[s] ++;
  13.         }
  14.         return res;
  15.     }
  16. };

974. Subarray Sums Divisible by K

题解

这道题的思路和上面的题目如出一辙，也是一个前缀和的问题。
题目里其实有一些小陷阱。
比如说推出了s[i] % k == s[j] % k之后，里面有一层引申含义是，等式左右两边的数值范围均为[0, k)
利用之前元素和现在元素前缀和的关系，很快的求得最终的答案。

代码

  1. class Solution {
  2. public:
  3.     int subarraysDivByK(vector<int>& nums, int k) {
  4.         vector<int> cnt(k, 0);
  5.         cnt[0] ++;
  6.         int res = 0;
  7.         for (int i = 1, s = 0; i <= nums.size(); i ++) {
  8.             s += nums[i - 1];
  9.             // (s[i] - s[j]) % k = 0;
  10.             // s[i] % k == s[j] % k;
  11.             int idx = s % k;
  12.             if (s < 0 && idx != 0) {
  13.                 idx += k;
  14.             }
  15.             res += cnt[idx];
  16.             cnt[idx] ++;
  17.         }
  18.         return res;
  19.     }
  20. };