开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 523】连续的子数组和

简介: 给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。
+关注继续查看

题目描述


给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。

示例1

输入:
[23,2,4,6,7], k = 6
输出:
True
解释:
[2,4] 是一个大小为 2 的子数组,并且和为 6。

示例2

输入:
[23,2,6,4,7], k = 6
输出:
True
解释:
[23,2,6,4,7]是大小为 5 的子数组,并且和为 42。

提示

  • 数组的长度不会超过 10000 。
  • 你可以认为所有数字总和在 32 位有符号整数范围内。

题解


暴力法



image.png

前缀和优化


image.png

求余优化


假设前缀和为 sum ,那么区间 [i, j] 的和就可以表示为 sum[j]-sum[i-1] ,如果它是 k 的倍数,就说明了 sum[j] 和 sum[i-1] 模 k 的余数是相同的。

那么我们就可以提前把 sum 数组里的每个数都对 k 求余,然后看有没有两个余数是相同的,并且距离大于等于 2 就行了。

这只需要用一个哈希表就可以判断一个数有没有在之前出现过了。如果一个数没有出现过,就把它的下标放进哈希表。否则的话就判断当前下标和哈希表中的下标差值,如果大于等于 2 ,就找到合法区间了,直接返回 true 。

代码


c++

class Solution {
    public:
    bool checkSubarraySum(vector<int>& nums, int k) {  
        int n = nums.size(); 
        if (n < 2) return false;    
        if (!k) {      
            for (int i = 1; i < n; ++i) { 
                if (!nums[i] && !nums[i-1]) { 
                    return true;  
                }   
            }   
            return false; 
        }    
        unordered_map<int, int> mp;    
        mp[0] = 0;   
        int sum = 0;  
        for (int i = 0; i < n; ++i) { 
            (sum += nums[i]) %= k;  
            if (mp.find(sum) == mp.end()) { 
                mp[sum] = i + 1;    
            } else if (i + 1 - mp[sum] >= 2) { 
                return true;   
            }      
        }     
        return false;
    }
};

python

class Solution: 
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:       
        n = len(nums) 
        if k == 0:  
            for i in range(1, n):  
                if nums[i] == 0 and nums[i-1] == 0: 
                    return True  
                return False 
            mp = {}   
            mp[0] = 0  
            sum = 0  
            for i in range(n):  
                sum += nums[i]
                sum %= k  
                if sum not in mp: 
                    mp[sum] = i + 1 
                    elif i + 1 - mp[sum] >= 2:
                        return True
                    return False

后记


c++ 有多种实现方法,可以用 map 、hash_map 、unordered_map 等多种数据结构。其中 hash_map 不在标准库里,这里没法使用。理论上 unordered_map 比 map 会快一点,但是实际运行中没有发现差别。

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
每日算法系列【LeetCode 992】K个不同整数的子数组
给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定独立的子数组为好子数组。(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。)
27 0
LeetCode(算法)- 297. 二叉树的序列化与反序列化
LeetCode(算法)- 297. 二叉树的序列化与反序列化
19 0
leetcode算法231.2 的幂
当给你一个整数 n时,如何判断该整数是否是 2 的幂次方?本文带大家解决这个问题。
12 0
LeetCode 算法题系列(第一周 25道)(下)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
38 0
LeetCode 算法题系列(第一周 25道)(上)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
25 0
【LeetCode13】罗马数字转整数(简单模拟+哈希)
简单题,读懂题意。如果右边的数比当前的数大,则当前数需要加个负号,如IV是5-1=4;如果右边的数比当前的数字小,则都是加法(注意最后一个数也是用加法的)。 三、代码
18 0
☆打卡算法☆LeetCode 88、合并两个有序数组 算法解析
“给定两个递增数组和两个代表数组长度的整数,合并两个数组,返回合并后递增顺序的数组。”
27 0
【算法千题案例】⚡️每日LeetCode打卡⚡️——53.两个数组的交集 II
📢前言 🌲原题样例:两个数组的交集 🌻C#方法:字典 🌻Java 方法:哈希 Java方法二:排序 + 双指针 💬总结
37 0
LeetCode刷题349-简单-两个数组的交集
LeetCode刷题349-简单-两个数组的交集
30 0
LeetCode刷题88-简单-合并两个有序数组
LeetCode刷题88-简单-合并两个有序数组
30 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载