【LeetCode每日一题】——523.连续的子数组和

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【题目提示】
  • 七【解题思路】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 前缀和

二【题目难度】

  • 中等

三【题目编号】

  • 523.连续的子数组和

四【题目描述】

  • 给你一个整数数组 nums 和一个整数 k ,如果 nums 有一个 好的子数组 返回 true ,否则返回 false
  • 一个 好的子数组 是:
    • 长度 至少为 2 ,且
    • 子数组元素总和为 k 的倍数。
  • 注意:
    • 子数组 是数组中 连续 的部分。
    • 如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 xk 的一个倍数。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 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
  • 0 < = n u m s [ i ] < = 1 0 9 0 <= nums[i] <= 10^9 0<=nums[i]<=109
  • 0 < = s u m ( n u m s [ i ] ) < = 2 31 − 1 0 <= sum(nums[i]) <= 2^{31} - 1 0<=sum(nums[i])<=2311
  • 1 < = k < = 2 31 − 1 1 <= k <= 2^{31} - 1 1<=k<=2311

七【解题思路】

  • 前缀和思想:设 prefix_sum[i] 表示数组 nums 的前缀和,即 prefix_sum[i] 表示 nums 从第 0 到第 i 的元素的和。对于任意两个下标 ij(i < j),子数组 nums[i+1:j+1] 的和可以表示为 prefix_sum[j] - prefix_sum[i]
  • 取模运算:我们需要找到两个前缀和 prefix_sum[j] 和 prefix_sum[i],使得它们的差 prefix_sum[j] - prefix_sum[i]k 的倍数。我们可以通过对前缀和取模的方式(哈希表)来简化这个问题:如果 prefix_sum[j] % k == prefix_sum[i] % k,那么 prefix_sum[j] - prefix_sum[i] 一定是 k 的倍数(同余定理)。
  • 边界情况处理:
    • 如果 k == 0,则子数组的和必须为 0,所以需要特判。
    • 由于子数组的长度至少为 2,所以当找到满足条件的前缀和时,还需要确保两个下标之间的距离大于等于 2
  • 最后返回结果即可
  • 具体细节可以参考下面的代码

八【时间频度】

  • 时间复杂度: O ( m ) O(m) O(m) m m m为传入的数组的长度
  • 空间复杂度: O ( m i n ( m , k ) ) O(min(m, k)) O(min(m,k)) m m m为传入的数组的长度, k k k为计算得到的余数的个数

九【代码实现】

  1. Java语言版
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        hashMap.put(0, -1);
        // 初始化前缀和
        int prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 更新前缀和
            prefixSum += nums[i];
            if (k != 0) {
                // 对 k 取模
                prefixSum %= k;
            }
            // 检查当前取模后的前缀和是否已经在哈希表中
            if (hashMap.containsKey(prefixSum)) {
                // 如果存在,并且下标差大于等于 2,则找到符合条件的子数组
                if (i - hashMap.get(prefixSum) > 1) {
                    return true;
                }
            } else {
                // 不存在则记录当前前缀和对应的下标
                hashMap.put(prefixSum, i);
            }
        }
        return false;
    }
}
  1. Python语言版
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
         # 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        hash_map = {0: -1}
        # 初始化前缀和
        prefix_sum = 0
        for i, num in enumerate(nums):
            # 更新前缀和
            prefix_sum += num
            if k != 0:
                # 对 k 取模
                prefix_sum %= k
            # 检查当前取模后的前缀和是否已经在哈希表中
            if prefix_sum in hash_map:
                # 如果存在,并且下标差大于等于 2,则找到符合条件的子数组
                if i - hash_map[prefix_sum] > 1:
                    return True
            else:
                # 不存在则记录当前前缀和对应的下标
                hash_map[prefix_sum] = i
        return False
  1. C++语言版
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        // 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        unordered_map<int, int> hashMap;
        hashMap[0] = -1;
        // 初始化前缀和
        int prefixSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 更新前缀和
            prefixSum += nums[i];
            if (k != 0) {
                // 对 k 取模
                prefixSum %= k;
            }
            // 检查当前取模后的前缀和是否已经在哈希表中
            if (hashMap.find(prefixSum) != hashMap.end()) {
                // 如果存在,并且下标差大于等于 2,则找到符合条件的子数组
                if (i - hashMap[prefixSum] > 1) {
                    return true;
                }
            } else {
                // 不存在则记录当前前缀和对应的下标
                hashMap[prefixSum] = i;
            }
        }
        return false;
    }
};

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. Python语言版
    在这里插入图片描述

  3. C++语言版
    在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/897160.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【不要离开你的舒适圈】:猛兽才希望你落单,亲人总让你回家,4个维度全面构建舒适圈矩阵

单打独斗的英雄时代已经落幕 抱团取暖才是社会寒冬的良策 自然界中&#xff0c;每个物种都占据着自己的领地和生存空间。 生态位的差异决定了它们的生存方式&#xff0c;一旦离开领地&#xff0c;失去群体的庇护&#xff0c;就会沦为野兽的美餐。 人类社会同样存在隐形圈层…

Nginx16-Lua扩展案例

零、文章目录 Nginx16-Lua扩展案例 1、ngx_lua案例 &#xff08;1&#xff09;需求 请求地址&#xff1a;http://192.168.119.161/getByGender?name张三&gender1Nginx接收到请求后&#xff0c;根据gender传入的值 如果gender传入的是1&#xff0c;则在页面上展示张三先…

初阶数据结构【3】--单链表(比顺序表还好的一种数据结构!!!)

本章概述 前情回顾单链表实现单链表彩蛋时刻&#xff01;&#xff01;&#xff01; 前情回顾 咱们在上一章博客点击&#xff1a;《顺序表》的末尾&#xff0c;提出了一个问题&#xff0c;讲出了顺序表的缺点——有点浪费空间。所以&#xff0c;为了解决这个问题&#xff0c;我…

Java项目-基于springboot框架的线上买菜系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…

WebGL编程指南 - 高级变换与动画基础

学习使用一个矩阵变换库&#xff0c;该库封装了矩阵运算的数学细节。快速上手使用该矩阵库&#xff0c;对图形进行复合变换。在该矩阵库的帮助下&#xff0c;实现简单的动画效果。 矩阵变换库&#xff1a;cuon-matrix.js OpenGL中的函数&#xff1a; 书中 cuon-matrix.js 函数…

go jwt 用户登录和返回用户信息 token ----important!!!

1.每一行代码都有详细注释&#xff0c;解释了其功能和作用。这些注释可以帮助你理解代码如何工作&#xff0c;特别是在处理用户登录、生成 JWT、验证 JWT 和返回用户信息的过程中。 package main // 指定这个文件是一个可执行程序import ("fmt" …

SSRF-利用dict协议-攻击redis

1.靶场准备&#xff1a; CTFHub-技能树-Web-SSRF-Redis协议 蚁剑AntSword 2.简述&#xff1a; 2.1 SSRF 服务器端请求伪造&#xff0c;存在一个url参数&#xff0c;一般用于图片上传、网页重定向等&#xff0c;我们可以控制url参数&#xff0c;去访问内网服务器的敏感内容…

运用AI实践|如何从AI工具提升工作效率实践

文章目录 引言关于1024这个数值Python 语言获取算法代码Java语言获取算法代码其他语言获取算法代码1024 的用途和功能总结 &#x1f4eb; 作者简介&#xff1a;「六月暴雪飞梨花」&#xff0c;专注于研究Java&#xff0c;就职于科技型公司后端工程师 &#x1f3c6; 近期荣誉&am…

FPGA学习(6)-基础语法参数化设计阻塞与非阻塞

目录 1.两种参数化不改变源文件&#xff0c;只改仿真文件的值 2.参数化设计实现模块的重用 2.1不用参数化方法 2.1.1源文件 2.1.2仿真文件 2.1.3仿真波形及实验 2.2 用参数方法 2.2.1调用之前写的led灯闪烁模块&#xff0c;在本源函数中&#xff0c;例化4次调用之前的模…

Nginx15-Lua扩展模块

零、文章目录 Nginx15-Lua扩展模块 1、ngx_lua模块概念 淘宝开发的ngx_lua模块通过将lua解释器集成进Nginx&#xff0c;可以采用lua脚本实现业务逻辑&#xff0c;由于lua的紧凑、快速以及内建协程&#xff0c;所以在保证高并发服务能力的同时极大地降低了业务逻辑实现成本。…

ECharts饼图-饼图纹理,附视频讲解与代码下载

引言&#xff1a; 在数据可视化的世界里&#xff0c;ECharts凭借其丰富的图表类型和强大的配置能力&#xff0c;成为了众多开发者的首选。今天&#xff0c;我将带大家一起实现一个饼图图表&#xff0c;通过该图表我们可以直观地展示和分析数据。此外&#xff0c;我还将提供详…

信号(二)【信号的产生】

目录 1. 键盘组合键2. kill 命令3. 系统调用4. 异常5. 软件条件6. Term 和 Core 的区别 本篇文章介绍五种信号产生的方式&#xff0c;键盘组合键、kill 命令、系统调用、代码异常&#xff08;进程异常&#xff09;、软件条件来产生信号。 1. 键盘组合键 信号&#xff08;一&a…

商汤科技十周年公布新战略,将无缝集成算力、模型及应用

10月18日&#xff0c;恰逢商汤科技十周年庆典&#xff0c;“2024商汤十周年国际论坛&#xff1a;迈向AI 2.0共融新时代”在香港科学园成功举办。 据「TMT星球」了解&#xff0c;来自全球的行业领袖、政府代表、AI专家共聚于此&#xff0c;共同探讨AI行业的未来。 活动上&…

Linux隐藏权限介绍

隐藏权限概览 在Linux系统中&#xff0c;有时即便是以root用户身份&#xff0c;你也可能遇到无法修改特定文件的情况。这种限制往往源自chattr命令的应用&#xff0c;该命令用于为文件或目录设置“隐藏权限”&#xff0c;即底层属性&#xff0c;以增强系统安全性。值得注意的是…

Standard IO

为了提高可移植性&#xff0c;将通用IO接口经过再封装就形成了标准IO&#xff0c;标准IO不仅适用于Unix环境&#xff0c;也兼容非Unix环境&#xff0c;这也是为什么说我们应该尽可能的使用标准IO&#xff0c;通用IO通过文件描述符fd来与文件交互&#xff0c;为了以示区分&#…

极氪MIX:一台只有你想不到,没有它做不到的“家用神车”

了解极氪品牌的朋友应该都知道 极氪一直都在尝试打破目前汽车或者生活的一些现状 更愿意创造一些破界、超前的产品 比如说将家庭城市通勤、假日露营、自驾旅行、户外垂钓、朋友相聚等多场景融入一个空间的极氪MIX 这款车突破了SUV或MPV车型形态的固有限制 前悬仅 865mm&am…

【ArcGIS Pro实操第八期】绘制WRF三层嵌套区域

【ArcGIS Pro实操第八期】绘制WRF三层嵌套区域 数据准备ArcGIS Pro绘制WRF三层嵌套区域Map-绘制三层嵌套区域更改ArcMap地图的默认显示方向指定数据框范围 Map绘制研究区Layout-布局出图 参考 本博客基于ArcGIS Pro绘制WRF三层嵌套区域&#xff0c;具体实现图形参考下图&#x…

Centos安装Nginx 非Docker

客户的机器属于 Centos7 系列&#xff0c;由于其较为陈旧&#xff0c;2024开始众多镜像和软件源都已失效。此篇文章将详细记录在 Centos7 操作系统上从零开始安装 Nginx 的整个流程。 本文Nginx是安装在/usr/local/nginx下 详细步骤如下&#xff1a; 准备Nginx安装包&#x…

安防监控摄像头图传模组,1公里WiFi无线传输方案,监控新科技

在数字化浪潮汹涌的今天&#xff0c;安防监控领域也迎来了技术革新的春风。今天&#xff0c;我们就来聊聊这一领域的产品——摄像头图传模组&#xff0c;以及它如何借助飞睿智能1公里WiFi无线传输技术&#xff0c;为安防监控带来未有的便利与高效。 一、安防监控的新篇章 随着…

程序员适合玩的游戏:《人力资源机器》提升编程思维【Human Resource Machine】

程序员适合玩的游戏&#xff1a;《人力资源机器》提升编程思维【Human Resource Machine】 在当今这个技术日新月异的时代&#xff0c;编程已经成为一门不可或缺的技能。对于程序员来说&#xff0c;不仅需要扎实的专业知识&#xff0c;还需要不断锻炼逻辑思维和解决问题的能力…