当前位置: 首页 > article >正文

算法:974.和可以被K整除的子数组

题目

链接:leetcode链接

在这里插入图片描述

思路分析(前缀和 + 同余定理)

首先,我们要了解一下什么是同余定理

同余定理:
如果(a - b)/ p = k …… 0
则 a % p == b % p

证明我写在草稿纸上,如下图:
在这里插入图片描述

初此之外,我们还需要理解一个问题
在C++/java中负数取模会怎么样呢?
比如 - 2 % 5等于多少呢?
按道理来说应该是3,但是C++/java里的答案是-2
这明显是需要进行修正的

如何进行修正呢?
我们只需要( a % p + p)% p
这样,无论是正数取模还是负数取模都不会出现问题。

OK,到这里前置知识讲完了,我们就正式开始讲思路了。

需要找一个子数组的和是k的倍数
那么只需要找两个区间的前缀和对k取模的余数相同即可。

和这道题的思路非常相似
传送门:560.和为k的子数组

我们利用滚动数组去求前缀和,
记录sum % k的余数
然后在[0,i-1]区间内去hash表中寻找一个区间的前缀和对k取模的结果与sum对k取模结果相同即可
将sum% k的余数放到hash表中(一定要是先查找在插入)

细节:
(1)什么时候插入hash表
一定要是先查找,在插入
(2)对于[0 , i]区间的和正好是K的倍数的情况如何处理
还是一样,我们先去把余数0提前先往hash表里插一个即可
具体原因可以查看和为k的子数组这篇文章

代码

//同余定理
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum = 0,ret = 0;
        unordered_map<int,int> hash;//hash表里面放余数

        hash[0] = 1;//这个0依旧是存的余数
        for(auto& e:nums)
        {
            sum += e;
            int check = (sum % k + k) % k; // 对余数进行修正很关键
            if(hash.count(check))  ret += hash[check]; 
            hash[check]++;
        }

        return ret;
    }
原文地址:https://blog.csdn.net/2303_78940834/article/details/142872188
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/348926.html

相关文章:

  • 大模型相关文章
  • 离宝安羊台山登山口最近的停车场探寻
  • Brave编译指南2024 MacOS篇-为Brave项目做出贡献(八)
  • Java基础概览和常用知识(六)
  • 理解智能合约:区块链在Web3中的运作机制
  • 人工智能风险预警以及区块链解决方案探索
  • simple_transfer攻防世界
  • 搭建个人博客--1、前端页面
  • 【哈希】1. leetcode 1. 两数之和
  • 鸿蒙--播放器状态控制
  • springcloud之基于RabbitMQ消息总线方式刷新配置服务
  • Linux下的杀毒软件介绍
  • 使用OpenCV实现基于EigenFaces的人脸识别
  • 道路车辆功能安全 ISO 26262标准(4-3)—系统级产品开发
  • KinDEL数据集:包含8100万个小分子的库,为激酶抑制剂的发现提供了一个丰富且功能强大的资源。
  • JavaScript前端开发技术
  • IDEA断点调试查看底层源码---程序员必备核心素养
  • Android设置状态栏隐藏、固定颜色
  • SpringBoot +Vue3前后端分离项目入门基础实例二
  • 运用 JDK8 中的核心新特性