前缀和变形 + 哈希表

统计趣味子数组的数目

解题思路:

设

\[s_i = \sum_{i = 1} ^ n{nums[i] \% module == k} \]

题目求满足$s_r - s_{l-1} \equiv k \pmod {module} $的子数组的个数。

公式转换:

\[\begin{align} &s_r - s_{l-1} \equiv k \pmod {module}\\ &(s_r - s_{l-1}) \%module = k\\ &((s_r \% module-s_{l-1}\%module)\%module + module)\%module = k\\ &s_r\%module - k = s_{l-1}\%module\\ &((s_r - k)\%module + module)\%module =s_{l-1}\%module \end{align} \]

由上述公式建立哈希表，单次遍历(因为$l<r$)判断即可。

时间复杂度: $O(n)$

代码:

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n = nums.size();
        unordered_map<long long,int> q;
        q[0] = 1;
        long long s = 0;
        long long ans = 0;
        for(int i = 0;i<n;i++)
        {
            s = (s + (nums[i] % modulo == k)) % modulo;
            ans += q[((s - k) % modulo + modulo) % modulo];
            q[s % modulo] ++;
        }
        return ans;
    }
};

和为 K 的子数组

解题思路:

设:

\[s_i = \sum_{i = 1} ^ i{nums[i]} \]

公式变换:

\[\begin{align} &s_r - s_{l-1} = k\\ &s_r - k = s_{l-1} \end{align} \]

时间复杂度: $O(n)$

代码:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<long long,int> q;
        q[0] = 1;
        int n = nums.size();
        long long s = 0;
        long long ans = 0;
        for(int i = 0;i<n;i++)
        {
            s += nums[i];
            ans += q[s - k];
            q[s] ++;
        }
        return ans;
    }
};

和可被 K 整除的子数组

解题思路:

设:

\[s_i = \sum_{i = 1} ^ i {nums[i]} \]

公式变换:

\[\begin{align} (s_r - s_{l-1}) \% k &= 0\\ s_r \% k &= s_{l-1}\%k \end{align} \]

代码:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        map<long long,int> q;
        q[0] = 1;
        long long s = 0;
        long long ans = 0;
        int n = nums.size();
        for(int i = 0;i<n;i++)
        {
            s = ((s + nums[i] % k) + k) % k;
            ans += q[s];
            q[s]++;
        }
        return ans;
    }
};

连续的子数组和

解题思路:

设:

\[s_i = \sum_{i = 1} ^ i {nums[i]} \]

公式变换:

\[\begin{align} (s_r - s_{l-1})\% k& = 0 ,&(r - i >=2)\\ s_r\%k &= s_{l-1}\%k,&(r-i>=2) \end{align} \]

代码:

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        map<long long,int> q;
        long long last = nums[0] % k;
        q[0] = 1;
        long long s = last;
        long long ans = 0;
        for(int i = 1 ;i<n;i++)
        {
            s = (s + nums[i]) % k;
            if(q.count(s))
            {
                return true;
            }
            q[last]++;
            last = s;
        }
        return false;
    }
};

连续数组

解题思路:

设:

\[s_i = \sum_{i=1}^i{nums[i] == 1} \]

公式变换:

\[\begin{align} 2*(s_r-s_{l-1})&=r-l+1\\ 2 *s_r-r&=2*s_{l-1}+1 \end{align} \]

代码:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<long long,long long> q;
        q[1] = -1;
        int n = nums.size();
        long long s = 0;
        long long cur = 0;
        long long ans = 0;
        for(int i = 0;i<n;i++)
        {
            s = s + nums[i];
            cur = 2 * s - i;
            if(q.count(cur))
            {
                ans = max(ans,i - q[cur]);
            }
            else
            {
                q[cur] = i;
            }
        }
        return ans;
    }
};