解决文章目录问题的话，dfs突发(超时)数组前缀和最终的状态压缩)压缩为了存储前缀的数组)版本问题2 )蓝桥杯例题)解题代码
主题1
解题同余定理：如果两个整数m，n满足n-m并能被k整除，则n和m对于k是同余的
即(pre(j )-pre ) I ) ) k==0时，pre ) j ) ) k==pre ) I ) ) k
导出=pre(I ) %k=(a0a1.AI ) ) k=) a0% ka1%k.AI%k ) ) k ) ) )此导出有助于简化前缀和当前前缀，其中% k是最后一个前缀和%
散列表存储key:pre(I ) % k
Value: i
导线测量流程：
计算前缀和pre(j ) % k
如果pre(j ) % k已经存在于散列表中，则此时存在的I满足pre(j ) % k==pre(i ) % k ) Ij )
HashMap中已知Key，可以取Value即I的值，最后判断j - i=2是否成立即可
如果散列表中不存在pre(j ) % k，则将(pre(j ) % k，j )存储在散列表中
(状态压缩)当计算pre(I )=(pre(I-1 ) nums[i] ) k时，因为pre(I )只与以前的状态有关，所以可以直接使用变量pre代替阵列。 求前缀和% k的表达式简化为问题解决代码remainder=(remainder nums[i] ) % k。
dfs搜索(超时)已超时，但缺少一个测试用例
时间复杂度o(n^2) ) ) ) ) ) ) ) ) )。
class solution { public : boolchecksubarraysum (vectorintnums，int k ) } t=k； //遍历所有子数组for (inti=0； inums.size (； I ) s=I； DFS(NUMS，I，0 )； if(RES )返回真； } return false； }private: bool res=false； int t； int s； voidDFS(vectorintnums，int k，int target ) if ) k-S1target%t==0) { res=true； 返回； }if(k==nums.size ) ) return； DFS(nums，k 1，target nums[k] )； }； 数组前缀和
时间复杂度o(n )空间复杂度o(n ) )。
class solution { public : boolchecksubarraysum (vectorintnums，int k )//前缀和vectorintpre ) nums.size )1)； unordered_mapint，inthash； //包括余数为0的在内，hash[0]=0； for(intI=1； i=nums.size (； I ) { pre[i]=pre[i-1] nums[i-1]； ///如果在取当前前缀和余数之前出现，则判断为真；否则判断为真(hashif(hash.count(pre ) I ) %k ) ) if ) I-hash(pre ) I ) %k )=2)； } else{ hash[pre[i]%k]=i； } } return false； }； 最终状态压缩(压缩用于存储前缀和的数组)版本
关于空间的复杂性也减少了4m。 实际上两者的复杂性都是一样的。
class solution { public : boolchecksubarraysum (vectorintnums，int k )//前缀和unordered_mapint，inthash； //包括余数为0的在内，hash[0]=0； int pre=0； for(intI=1； i=nums.size (； I ) { pre=pre nums[i-1]； //如果当前前缀和余数之前出现，则判断当前前缀和余数；否则，判断hashif(hash.count ) pre%k ) ) if(I-hash[pre%k]=2)返回trurn trure； } else{ hash[pre%k]=i； } } return false； }； 主题2 (蓝桥杯例题) )。
唯一的不同是，需要求出这样的区间和存在的次数，在前面的问题的基础上变更保存在hash表中的值即可。 这个问题显然需要记录某个同余的出现次数，如果再次发生同余，就会发生同余次数的区间个数(因为这个问题我们承认区间长为1 )。
坑：注意前缀和用int型会爆，还有结果用int也会爆，所以都用long long型即可。
由于解题代码蓝桥杯练习系统不支持C 11，因此需要在unordered_map中调用tr1库的命名空间，还需要tr1。
# include bits/stdc.h # include tr1/unordered _ mapusingnamespacestd； using namespace std:tr1； longlongsubarraysum (vectorintnums，int k )//前缀和unordered_mapint，inthash； //包括余数为0的在内，hash[0]=1； 长龙预=0； 长龙RES=0； for(intI=1； i=nums.size (； I ) { pre=pre nums[i-1]； //如果出现在取当前前缀和余数之前，更新答案，如果有多少个相同的余数对象，就有多少个答案if(hash.count(pre%k ) ) RES=hash ) pre%k )； ) } hash[pre%k]； } return res； (}int main ) ) {int n，k； cinnk； vtorintnums(n； for(intI=0； in； I ) cinnums[i]； 长整型RES=subarray sum (nums，k )； coutres return 0； }