LeetCode——523. 连续的子数组和

题目简介

题干：
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
子数组大小 至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

示例1：
输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例2：
输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例3：
输入：nums = [23,2,6,4,7], k = 13
输出：false

题解思路

判断是否存在k倍数的大小不小于2的子数组，最近是前缀和“元月”，一下子就联想到了前缀和求解

因为结果就是k的倍数，所以只需要找到各种组合所差的元素是否存在，做一个前缀和集合就可以用哈希表找到

但是这里最不容易想到的是如何生成各种组合的子数组，我们这里采用了取余的方法

取余可以做什么呢，可以把组合好的子集的和与下一个元素自动合并，总是返回相差的元素

正确代码

class Solution {
    //前缀和与哈希表
    public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        //规定空的前缀的结束下标为 -1，由于空的前缀的元素和为 0
        map.put(0, -1);
        //余数标志
        int remainder = 0;
        for (int i = 0; i < len; i++) {
            //获得余数
            //关键在于每次取余都可以返回当前所有的集合种类与k的倍数的差
            remainder = (remainder + nums[i]) % k;
            //如果存在余数则判断数组大小是否为大于等于2，因为下标是从-1开始
            //如果不存在则在map中添加余数
            if (map.containsKey(remainder)) {
                int prevIndex = map.get(remainder);
                if (i - prevIndex >= 2) {
                    return true;
                }
            } else {
                map.put(remainder, i);
            }
        }
        return false;
    }
}

总结

事实告诉我们，只要做的多就会有感觉，遇到问题你的直觉就会告诉你该用何种方法解决

这里其实也有dp的思想，但是自己不太确定是不是，并且还有很多可以优化的办法，大家可以继续尝试

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见

PS：昨天是六一儿童节呀，迟到的六一祝福送给所有同行和喜欢编程的朋友们，祝我们永远年轻

LeetCode——523. 连续的子数组和

原文：https://www.cnblogs.com/bc-song/p/14839973.html