首页 > 编程语言 >力扣523(java)-连续的子数组和(中等)

力扣523(java)-连续的子数组和(中等)

时间:2022-10-18 15:33:14浏览次数:54  
标签:map java nums int 523 力扣 数组 rem true

题目:

给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

子数组大小 至少为 2 ,且
子数组元素总和为 k 的倍数。
如果存在,返回 true ;否则,返回 false 。

如果存在一个整数 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 <= 105
0 <= nums[i] <= 109
0 <= sum(nums[i]) <= 231 - 1
1 <= k <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/continuous-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

前缀和+HashMap:

1.计算前缀和,创建一个HashMap,其中的key为前缀和对k取余后是余数,value为对应的index索引位置;

2.如果在哈希表中存在有当前相同的前缀余数,取出其value,并且与当前index距离大于等于2,则说明符合题目要求,返回true,如果小于2,则继续遍历;

3.如果不存在则将当前余数与其对应的下标index存储在哈希表中。

图来自@小虎

 注意:加入map.put(0, -1)是为了把边界值也考虑进入,不用在特殊考虑。

java代码:

 1 class Solution {
 2     public boolean checkSubarraySum(int[] nums, int k) {
 3         Map<Integer, Integer> map = new HashMap<>();
 4         map.put(0, -1);
 5         int prefixsum = 0, rem = 0;
 6         for(int i = 0; i < nums.length; i++){
 7             prefixsum += nums[i];
 8             rem = prefixsum % k;
 9             if(map.containsKey(rem)){
10                 if(i - map.get(rem) >= 2){
11                     return true;
12                 }
13             }else{
14                 map.put(rem, i);
15             }
16         }
17         return false;
18     }
19 }

 python代码:

 1 class Solution:
 2     def checkSubarraySum(self, nums: List[int], k: int) -> bool:
 3         map = {}
 4         map[0] = -1
 5         prefixSum, rem = 0, 0
 6         for i in range(len(nums)):
 7             prefixSum += nums[i]
 8             rem = prefixSum % k
 9             if rem in map:
10                 if (i - map[rem] >= 2):
11                     return True
12             else:
13                 map[rem] = i
14         return False

标签:map,java,nums,int,523,力扣,数组,rem,true
From: https://www.cnblogs.com/liu-myu/p/16802702.html

相关文章

  • Java并发编程学习7-阻塞队列
    阻塞队列介绍阻塞队列之前,先来介绍下队列Queue。Queue用来临时保存一组等待处理的元素。它提供了几种非阻塞队列实现,如下:ConcurrentLinkedQueue,这是一个传统的先进先出......
  • JavaScript 获取两个时间相差的周数
    exportfunctiongetWeek(date1,date2){letd1=newDate(date1);letd2=newDate(date2);console.log(Math.ceil(parseInt(((d2-d1)/(1000*3......
  • java学习笔记38
    面向对象什么是多态1.多态概述多态是继封装、继承之后,面向对象的第三大特性。2.多态现实意义理解:现实事物经常会体现出多种形态,如学生,学生是人的一种,则一个具体的同学......
  • Java数据结构_Collection类
     双链表结构     LinkedList可以完成队列结构栈结构(双向链表)栈对头结点进行add和removepop的底层就是pu......
  • JAVA项目中常见的异常处理汇总
    在进行JAVA项目开发时,不免会遇到一些比较常见的异常处理情况,下面是我通过在网上查询了一些相关资料进行的各种异常处理情况的总结1.字符串转化为数字的异常(Java.lang.Numb......
  • Java代码审计sql注入
    java_sec_code该项目也可以叫做JavaVulnerabilityCode(Java漏洞代码)。每个漏洞类型代码默认存在安全漏洞(除非本身不存在漏洞),相关修复代码在注释里。具体可查看每个漏......
  • JavaScript的日期对象的使用Date
    1<script>2letdate=newDate();//返回的是当前的时间3console.log(date.getFullYear());//获取的当前年份4console.log(date.getMonth()+1);......
  • Java8Stream的flatmap应用(区别map)-优化嵌套for循环条件筛选
    场景Java8新特性-Stream对集合进行操作的常用API:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/126070657前面讲Stream的常用api中讲到map的使用......
  • Java基于解释器模式实现定义一种简单的语言功能示例
    本文实例讲述了Java基于解释器模式实现定义一种简单的语言功能。分享给大家供大家参考,具体如下:一模式定义解释器模式:就是给定一个语言的文法表示,并且定义一个解释器,用来......
  • Java类加载机制(classloader)
    什么是classloaderclassloader顾名思义,即是类加载。虚拟机把描述类的数据从class字节码文件加载到内存,并对数据进行检验、转换解析和初始化,最终形成可以被虚拟机直接使用......