leetcode 523.连续的子数组的和——前缀和+哈希表

本文主要是介绍leetcode 523.连续的子数组的和——前缀和+哈希表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

523.连续的子数组的和

题目

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

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。
  如果存在，返回 true ；否则，返回 false 。
  如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

示例

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

题解 （ 前缀和+哈希表）

• 方法一，暴力解超时
  
• 方法二：前缀和+哈希表

代码：

class Solution {public boolean checkSubarraySum(int[] nums, int k) {//前缀和+哈希表int m=nums.length;if(m<2){return false;}Map<Integer,Integer> map=new HashMap<Integer,Integer>();map.put(0,-1);int remainder=0;for(int i=0;i<m;++i){remainder=(remainder+nums[i])%k;if(map.containsKey(remainder)){int preIndex=map.get(remainder);if(i-preIndex>=2){return true;}}else{map.put(remainder,i);}}return false;}
}

类似的（前缀和+哈希表）的题目

525. 连续数组https://leetcode-cn.com/problems/contiguous-array/

这篇关于leetcode 523.连续的子数组的和——前缀和+哈希表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---