题解

• 今天的题咋眼一看就感觉是前缀和+哈希表
• 但没想好怎么用就先暴力解了，果然超时

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        for(int i=0;i<nums.length-1;i++){
            int sum = nums[i];
            for(int j = i+1;j<nums.length;j++){
                sum+=nums[j];
                if(sum%k==0)return true;
            }
        }
        return false;
    }
}

• 根据题意数组长度至少为2才能有符合的子数组
• 如果两个数求模同一个数余数相等，那么它们的差是这个模数的倍数(这个点想到就能解了)

这样就可以用前缀和+哈希表的方式解题，哈希表存储余数第一次出现的位置，第二次出现且相隔一个元素就意味着有子数组的和是k的倍数

• 注意和其他前缀和解法一样，这里也要先规定初始条件，前0项和余数为k下标-1
• 找到余数相等的前缀和只有相隔一个元素才行，考虑下面情况

• 关于这点官方题解这么描述的

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if(nums.length<2)return false;
        Map<Integer, Integer> map = new HashMap<>();
            int rem = 0;
            map.put(0, -1);
            for (int i = 0; i < nums.length; i++) {
                rem = ( rem+nums[i])%k;
                if (map.containsKey(rem)) {
                    if((i-map.get(rem))>1)return true;
                }else{
                    map.put(rem, i);
                }
            }
            return false;
    }
}

一点屁话

• 前缀和+哈希表的解法也不是第一次遇到了，感觉难在找子数组之间的关系
• 尝试固定一个题解模板
• 💊