和可被K整除的子数组(Java详解)

这篇具有很好参考价值的文章主要介绍了和可被K整除的子数组(Java详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、题目描述

二、题解

思路分析

具体实现

完整代码


一、题目描述

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。

子数组 是数组的 连续 部分。

示例:

输入:nums = [4,5,0,-2,-3,1],k = 5

输出:7

输入:nums = [ 5 ],k = 9

输出:0

二、题解

思路分析

首先我们很容易想到暴力枚举的方法,即遍历数组,在遍历每个元素的同时向后寻找元素之和能够被k整除的子数组

暴力枚举代码如下:

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
       int ret = 0;
       for(int i = 0; i < nums.length; i++){
           int sum = 0;
           for(int j = i; j < nums.length; j++){
               sum += nums[j];
               if(sum % k == 0){
                   ret++;
               }
           }
       }
       return ret;
    }
}

其时间复杂度为O(),当输入的nums数组较大时,会超出时间限制,因此,暴力枚举方式行不通,我们继续考虑其他方法

题目中要求我们找到元素之和可被k整除的(连续、非空)子数组,因此我们可以想到使用双指针的思路,即考虑使用滑动窗口来解决这个问题,然而,本题不能使用滑动窗口来解决

为什么不能使用滑动窗口?

参照示例1,其输入的数组 nums = [4,5,0,-2,-3,1],其中不仅有正整数,还有零和负数,

在使用滑动窗口时,当窗口内元素满足条件时,要移动left指针,向前滑动窗口,但在本题中,由于有零和负整数,在窗口内元素满足条件时,不能移动left指针,因为下一个元素可能是零,加入后任满足条件,也可能几个元素相加等于0,加入后也满足条件。因此,若是使用滑动窗口来解决本题,则会漏掉一些符合情况的子数组。

滑动窗口的思路也不行,我们继续思考新的方法,在涉及子数组问题时,我们也常使用前缀和来解决问题

什么是前缀和?

前缀和即某序列的前n项和,类似于数学中的数列前n项和。即从首元素位置到i位置这个区间内所有元素之和,前缀和只是一种思路,其不仅可以求和,也可以求从首元素位置到i位置区间内的乘积等等。

我们以示例1为例子,先求前缀和数组,再通过前缀和数组来求解子数组,

和可被K整除的子数组(Java详解),Java刷题,算法,数据结构,leetcode,前缀和,哈希表

然而,在这种情况下,当我们求解子数组时,仍然需要后遍历,求得从i到j位置的元素之和,再判断其是否符合条件,

和可被K整除的子数组(Java详解),Java刷题,算法,数据结构,leetcode,前缀和,哈希表

其时间复杂度仍是O()

在通过前缀和数组求解子数组时,我们可以考虑向前遍历,即i位置上的元素为到i位置的元素之和

和可被K整除的子数组(Java详解),Java刷题,算法,数据结构,leetcode,前缀和,哈希表

此时,若以i位置为结尾的区间内的元素能够被被k整除,则

和可被K整除的子数组(Java详解),Java刷题,算法,数据结构,leetcode,前缀和,哈希表

 此时dp[i] - dp[j] = mk,(m为系数),即dp[i]与dp[j]同余(dp[i]取余 k 与dp[j]取余 k 的余数相同)(两数余数相同,在相减时就将余数消去,剩下的数便能整除k),此时,我们只需要找到,在i位置之前有多少个前缀和元素的余数与其前缀和相同,就能够得到以i位置为结尾的且能够被k整除的子数组个数。

然而,在求i位置之前有多少个前缀和元素的余数与其相同时,我们还需要再向前遍历一遍前缀和数组吗?

我们可以使用哈希表,存储前缀和元素的余数及其个数,这样,便只需要计算dp[i]的余数,再从哈希表中找到相同余数的元素个数,就可知道以i位置为结尾的且能够被k整除的子数组个数了。

在分析完思路后,我们来考虑其具体实现过程:

具体实现

首先我们需要一个哈希表,以前缀和元素模k的值为键,值的个数为值

// key:模k的的值,value:key的个数
Map<Integer, Integer> hash = new HashMap<>();

需要注意的是,在模k时,如果元素为负数,求出的值也为负数(例如 -4 % 5 = -4,-4 与 1 是同余的,若我们在哈希表中保存(-4, 1),而 % i的结果为 1,并在哈希表中找到结果为1的元素个数,此时就漏掉了结果 为 -4 的情况),

因此我们需要对其进行处理,将其变为正数,可以将其+k,使其变成正数,即 dp[i] % k + k(-4 + 5 = 1);当其为正数的时候则不需要 +k,若想要无需对元素进行正负数判断,则可在 +k 后再取余k,即 (dp[i] % k + k) % k,此时,若元素为正数,在 +k 后结果大于k,再对结果进行取余,又将其变为正确结果((3 % 5 + 5)% 5);若元素为负数,在 +k 后将负数变为正数,即正确结果,再对结果进行取余,仍是正确结果((-4 % 5 + 5)% 5)

求出数组的前缀和数组

由于哈希表中保存的是模k的值及其个数,因此我们不需要再创建一个前缀和数组用来保存前缀和,只需使用变量sum 来保存前i-1个元素的和

何时将结果放到哈希表中?

我们要从哈希表中找到相同余数的元素个数,从而知道以i位置为结尾的且能够被k整除的子数组个数,因此哈希表中不能存放i位置之后的元素结果,因此,每遍历一个元素,就将其结果更新到哈希表中

然而,此时还有一个细节问题

若以i位置为结尾的数组本身便能被k整除,此时模k的结果为 0,即从0位置到i位置的子数组之和能够被k整除,则在第一次出现该情况时,哈希表内没有key = 0的元素,会漏掉该结果,因此,我们需要处理这种特殊情况,即手动将(0, 1)放入哈希表中

完整代码

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // key:模k的的值,value:key的个数
       Map<Integer, Integer> hash = new HashMap<>();
       //处理特殊情况
        hash.put(0,1);
        int ret = 0;//子数组的个数
        int sum = 0;//用来保存前i-1个元素之和
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            //求出与 前i个元素之和 同余的元素个数
            int same = hash.getOrDefault((sum % k + k) % k, 0);
            ret += same;//更新结果
            hash.put((sum % k + k) % k,same + 1);//更新哈希表
        }
        return ret;
    }
}

题目来自:

974. 和可被 K 整除的子数组 - 力扣(LeetCode)文章来源地址https://www.toymoban.com/news/detail-788694.html

到了这里,关于和可被K整除的子数组(Java详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 「优选算法刷题」:长度最小的子数组

    给定一个含有  n   个正整数的数组和一个正整数  target  。 找出该数组中满足其总和大于等于   target   的长度最小的  连续子数组   [numsl, numsl+1, ..., numsr-1, numsr]  ,并返回其长度 。 如果不存在符合条件的子数组,返回  0  。 示例 1: 示例 2: 示例 3: 这道题也是一道

    2024年01月23日
    浏览(38)
  • Leetcode刷题详解——长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 提示: 1 = target = 109 1 = nums.length

    2024年02月07日
    浏览(49)
  • 算法刷题营【Day2】:: 双指针算法应用:滑动窗口 :209. 长度最小的子数组

    本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识! 目录: 1. 开篇例题:209. 长度最小的子数组 2. 题解参考 - - 2.1 方法一:暴力法 - - 2.2 方法二:滑动窗口 3. 方法思路点拨:滑动窗口 - - 3.1 直白解释 - - 3.2 本题思路点拨 4. 相关题集 1. 开篇例题:209. 长度

    2024年02月04日
    浏览(47)
  • 【1262. 可被三整除的最大和】

    来源:力扣(LeetCode) 描述: 给你一个整数数组 nums ,请你找出并返回能被三整除的元素最大和。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 4 * 10 4 1 = nums[i] = 10 4 方法:贪心 + 正向思维 我们把数组中的数分成三部分 a, b, c,它们分别包含所有被 3 除余 0 , 1, 2 的数。显

    2024年02月10日
    浏览(38)
  • 【1015. 可被 K 整除的最小整数】

    来源:力扣(LeetCode) 描述: 给定正整数 k ,你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。 返回 n 的长度。如果不存在这样的 n ,就返回 -1 。 注意: n 不符合 64 位带符号整数。 示例 1: 示例 2: 示例 3: 提示: 1 = k = 10 5 方法:遍历 思路与算法 题

    2024年02月03日
    浏览(71)
  • 长度最小的子数组(Java详解)

    目录 题目描述 题解 思路分析 暴力枚举代码 滑动窗口代码 给定一个含有  n   个正整数的数组和一个正整数  target  。 找出该数组中满足其和   ≥ target   的长度最小的  连续子数组   [numsl, numsl+1, ..., numsr-1, numsr]  ,并返回其长度 。 如果不存在符合条件的子数组,返回

    2024年02月05日
    浏览(35)
  • LeetCode 1262. 可被三整除的最大和

    力扣题目链接:https://leetcode.cn/problems/greatest-sum-divisible-by-three/ 给你一个整数数组  nums ,请你找出并返回能被三整除的元素最大和。   示例 1: 示例 2: 示例 3:   提示: 1 = nums.length = 4 * 10^4 1 = nums[i] = 10^4 一个数对3取模,只有0、1、2这三种情况。 我们只需要对nums中所有数

    2024年02月09日
    浏览(34)
  • Leetcode【1010】总持续时间可被 60 整除的歌曲

    最近忙于毕设,leetcode也就随缘刷刷每日一题了。 在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。 返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望下标数字 i 和 j 满足 i j 且有 (time[i] + time[j]) % 60 == 0 。 示例1: 来源:力扣(LeetCode) 链

    2024年02月03日
    浏览(79)
  • LeetCode——可被三整除的偶数的平均值

    #全国科技者工作日—为创新和未来而努力# 目录 1、题目  2、题目解读  3、代码 2455. 可被三整除的偶数的平均值 - 力扣(Leetcode) 给你一个由正整数组成的整数数组  nums  ,返回其中可被  3  整除的所有偶数的平均值。 注意: n  个元素的平均值等于  n  个元素  求和  

    2024年02月09日
    浏览(34)
  • leetcode分类刷题:易混题辨析一、209. 长度最小的子数组 vs 560. 和为K的子数组

    1、刷题慢慢积累起来以后,遇到相似的题目时,会出现算法思路混淆了 2、这两道题都是对 连续子数组加和 进行考察,细节区别在于数组元素在209. 长度最小的子数组为 正整数(窗口增加元素递增,减少元素递减) ,在560. 和为K的子数组为 整数 3、209. 长度最小的子数组采

    2024年02月10日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包