首页 > 其他 > 详细

前綴和

时间:2021-06-06 00:40:48      阅读:17      评论:0      收藏:0      [点我收藏+]

523. 连续的子数组和

难度中等

给你一个整数数组 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


解题思路:使用前缀和+ 哈希。
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;
    }
}

 

525. 连续数组

难度中等

给定一个二进制数组 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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!