连续的子数组和

Trace

6.2 每日一题

传送门：https://leetcode-cn.com/problems/continuous-subarray-sum/

Problem

暴力

枚举起点，枚举终点，计算区间和，时间复杂度$O(n^3)​$

计算区间和改用前缀和，时间复杂度$O(n^2)​$

前缀和+哈希表

记前缀和数组为$q[N]$，下标$i$到下标$j$的区间和为$q[j]-q[i-1]$，假如$(q[j]-q[i-1])$为$k$的倍数。

则$q[i-1]$和$q[j]$对$k$取余的结果相同。

因此，只需要求出每一位的前缀和对$k$取余的结果就好，这里采用哈希表来降低时间复杂度。哈希表的$key$为余数，$value$为这个余数第一次出现的索引。

在程序中遍历一次前缀和数组（前缀和数组可以直接存前缀和余数），如果在哈希表中没有出现，则存入哈希表；如果出现过可以判断索引差是否大于等于2（题设要求子数组长度至少为2），此时不需要更新哈希表。

注意：要将余数为0存入前缀和的第一项，保证遍历过程中如果遇到前缀和余数为0可以返回true。

程序

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int q[(int)1e5+10];
        q[0] = 0;
        for(int i=0;i<nums.size();i++){
            q[i+1]=(q[i]+nums[i])%k;
            cout<<q[i+1]<<" ";
        }
        map<int,int> mp;
        mp[0]=0;
        for(int i=1;i<=nums.size();i++){
            int tnt=q[i];
            if(mp.count(tnt)==0){
                mp[tnt]=i;
            }
            else if((i-mp[tnt])>=2){
                    return true;
            }

        }
        return false;
    }
};