首页 > 其他分享 >LeetCode 523. 连续的子数组和

LeetCode 523. 连续的子数组和

时间:2024-07-08 16:28:46浏览次数:15  
标签:下标 nums int record 数组 523 presum LeetCode

523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ,如果 nums 有一个 好的子数组 返回 true ,否则返回 false

一个 好的子数组 是:

  • 长度 至少为 2 ,且
  • 子数组元素总和为 k 的倍数。

注意

  • 子数组 是数组中 连续 的部分。
  • 如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 x 是 k 的一个倍数。0 始终 视为 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

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= sum(nums[i]) <= 2^31 - 1
  • 1 <= k <= 2^31 - 1

解法1:前缀和 + 哈希集

我们需要从 k 的倍数作为切入点来做。

预处理前缀和数组 presum,方便快速求得某一段区间的和。然后假定 [i,j] 是我们的目标区间,那么有:

presum[j] − presum[i−1]=n∗k
经过简单的变形可得:
要使得两者除 k 相减为整数,需要满足 presum[j] 和 presum[i−1] 对 k 取余相同。

也就是说,我们只需要枚举右端点 j,然后在枚举右端点 j 的时候检查之前是否出现过左端点 i,使得 presum[j] 和 presum[i−1] 对 k 取余相同。

具体的,使用 HashSet 来保存出现过的值。

让循环从 2 开始枚举右端点(根据题目要求,子数组长度至少为 2),每次将符合长度要求的位置的取余结果存入 HashSet。

如果枚举某个右端点 j 时发现存在某个左端点 i 符合要求,则返回 True。

Java版:

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] presum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i - 1] + nums[i - 1];
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 2; i <= n; i++) {
            set.add(presum[i - 2] % k);
            if (set.contains(presum[i] % k)) {
                return true;
            }
        }
        return false;
    }
}

Python3版:

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        presum = [0] * (n + 1)
        for i in range(1, n + 1):
            presum[i] = presum[i - 1] + nums[i - 1]
        record = set()
        for i in range(2, n + 1):
            record.add(presum[i - 2] % k)
            if presum[i] % k in record:
                return True
        return False

复杂度分析

  • 时间复杂度:O(n),n 是数组 nums 的长度。
  • 空间复杂度:O(n),n 是数组 nums 的长度。

解法2:前缀和 + 哈希表

如果事先计算出数组 nums 的前缀和数组,则对于任意一个子数组,都可以在 O(1) 的时间内得到其元素和。用 prefixSums[i] 表示数组 nums 从下标 0 到下标 i 的前缀和,则 nums 从下标 p+1 到下标 q(其中 p<q)的子数组的长度为 q−p,该子数组的元素和为 prefixSums[q]−prefixSums[p]。

如果 prefixSums[q]−prefixSums[p] 为 k 的倍数,且 q−p≥2,则上述子数组即满足大小至少为 2 且元素和为 k 的倍数。

当 prefixSums[q]−prefixSums[p] 为 k 的倍数时,prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同。因此只需要计算每个下标对应的前缀和除以 k 的余数即可,使用哈希表存储每个余数第一次出现的下标。

规定空的前缀的结束下标为 −1,由于空的前缀的元素和为 0,因此在哈希表中存入键值对 (0,−1)。对于 0≤i<m,从小到大依次遍历每个 i,计算每个下标对应的前缀和除以 k 的余数,并维护哈希表:

如果当前余数在哈希表中已经存在,则取出该余数在哈希表中对应的下标 prevIndex,nums 从下标 prevIndex+1 到下标 i 的子数组的长度为 i−prevIndex,该子数组的元素和为 k 的倍数,如果 i−prevIndex≥2,则找到了一个大小至少为 2 且元素和为 k 的倍数的子数组,返回 true;

如果当前余数在哈希表中不存在,则将当前余数和当前下标 i 的键值对存入哈希表中。

由于哈希表存储的是每个余数第一次出现的下标,因此当遇到重复的余数时,根据当前下标和哈希表中存储的下标计算得到的子数组长度是以当前下标结尾的子数组中满足元素和为 k 的倍数的子数组长度中的最大值。只要最大长度至少为 2,即存在符合要求的子数组。

Java版:

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

Python3版:

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        record = dict()
        presum = 0
        record[0] = -1 
        for i, num in enumerate(nums):
            presum = (presum + num) % k
            if presum in record:
                if i - record[presum] >= 2:
                    return True
            else:
                record[presum] = i 
        return False

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 nums 的长度。需要遍历数组一次。
  • 空间复杂度:O(min(n,k)),其中 n 是数组 nums 的长度。空间复杂度主要取决于哈希表,哈希表中存储每个余数第一次出现的下标,最多有 min(n,k) 个余数。

标签:下标,nums,int,record,数组,523,presum,LeetCode
From: https://blog.csdn.net/m0_56090828/article/details/140266567

相关文章

  • LeetCode 974. 和可被 K 整除的子数组
    974.和可被K整除的子数组给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。子数组 是数组中 连续 的部分。示例1:输入:nums=[4,5,0,-2,-3,1],k=5输出:7解释:有7个子数组满足其元素之和可被k=5整除:[4,5,0......
  • 01.数组
    在Go语言中,数组是一种固定长度的序列,它可以存储相同类型的元素。下面详细介绍数组的定义、初始化、访问和操作。数组的定义数组的定义语法为:[n]T,其中n表示数组的长度,T表示数组元素的类型。packagemainimport"fmt"funcmain(){//定义一个长度为5的整数......
  • C语言 指针和数组——指针数组的应用:命令行参数
    目录命令行参数演示命令行参数与main函数形参间的关系命令行参数什么是命令行参数(CommandLineArguments)?GUI界面之前,计算机的操作界面都是字符式的命令行界面(DOS、UNIX、Linux)例如,在DOS下拷贝文件用copyfile1.cfile2.c不......
  • 二位数组
    #include<iostream>//二维数组在函数中的传递//1.一维数组//2.函数√//3传递的方式√//4.返回二维数组usingnamespacestd;intmain(){ /* 1.二维数组的初始化定义: inta[][];//定义方式错误,编译不成功 intb[][2];//定义方式错误 intc[2][];//定义方式错误......
  • JS根据json数组多个字段排序及json数组常用操作
    本文转载自:https://www.jb51.net/article/162623.htm js根据json数组多个字段排序的实现代码如下所示:1/**数组根据数组对象中的某个属性值进行排序的方法2*使用例子:newArray.sort(sortByArr(['number'],false))//表示根据number属性降序排列;若第二个参数不传递,默......
  • [LeetCode] 134. Gas Station
    想到了提前判断和小于0的情况,懒得写,果然被阴间用例10万个加油站坑了。classSolution:defcanCompleteCircuit(self,gas:List[int],cost:List[int])->int:#1n=len(gas)ifn==1:ifgas[0]>=cost[0]:ret......
  • LeetCode 算法:岛屿数量 c++
    原题链接......
  • [LeetCode] 238. Product of Array Except Self
    坑真的很多,首先要处理全零reduce没有值typeerror的问题。classSolution:defproductExceptSelf(self,nums:List[int])->List[int]:total=reduce(mul,nums)ret=[]iftotal==0:try:total=reduce(mul,[......
  • 刷爆leetcode第九期
    题目一单值二叉树如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时,才返回true;否则返回false。题目图片如下我们这里主要是判断下根的值和它的左孩子还有右孩子相不相等如果相等返回true如果不相等返回false(当然这里还需要......
  • 刷爆leetcode第十期
    题目一相同的树给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。首先我们要来判断下它们的根是否相等根相等的话是否它们的左子树相等是否它们的右子树相等一直到子树为空为止大......