给你一个整数数组 nums
和一个整数 k
,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:
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
解题思路:使用前缀和+ 哈希。
class Solution { public boolean checkSubarraySum(int[] nums, int k) { if(nums.length <= 1) { return false; } Map<Integer, Integer> numPos = new HashMap<>(); numPos.put(0, -1); int total = 0; for(int i = 0; i < nums.length; i++) { total += nums[i]; int rest = total % k; if(numPos.containsKey(rest)) { if(i - numPos.get(rest) >= 2) { return true; } } else { numPos.put(rest, i); } } return false; } }
给定一个二进制数组 nums
, 找到含有相同数量的 0
和 1
的最长连续子数组,并返回该子数组的长度。
示例 1:
输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
class Solution { public int findMaxLength(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int count = 0; map.put(0, -1); int maxLen = 0; for(int i = 0; i < nums.length; i++) { count += nums[i] == 0 ? -1 : 1; if(map.containsKey(count)) { maxLen = Math.max(maxLen, i - map.get(count)); } else { map.put(count, i); } } return maxLen; } }
原文:https://www.cnblogs.com/billyqiu/p/14853871.html