前缀和

62 views

前缀和与哈希表

leetcode 523
题意：问是否存在子数组（长度大于1）的和能被k整除。
前缀和的经典问题，务必掌握。
子数组的和可以表示为两个前缀和相减的形式，看到整除第一反应应该是对k求余余数为0，因此推出两个前缀和关于k同余。
把前面的前缀和对k对余数加入哈希表，遍历前缀和的时候O(1)查找