前缀和第二弹-阿里云开发者社区

前缀和第二弹

2024-06-05 11

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 前缀和第二弹

力扣560.和为k的子数组

子数组经典暴力解法：枚举全部位置，因为取值为可能为负

首先把前缀和，和出现的次数都存储一下，一般前缀和就出现一次，然后往后找，如果前缀和-k就说明有一段数组是等于sum-k

class Solution {
    public int subarraySum(int[] nums, int k) {
        //前缀和  字符串组成sum次数
    Map<Integer,Integer>hash=new HashMap<>();
    hash.put(0,1);
    //ret统计最终结果，sum表示前一个位置的前缀和
    int sum=0;
    int ret=0;
    for(int m:nums){
        //sum+=表示当前位置前缀和
        sum+=m;
        //统计结果
        ret+=hash.getOrDefault(sum-k,0);
        hash.put(sum,hash.getOrDefault(sum,0)+1);
 
    }
    return ret;
    }
}

力扣974.和可被K整除的子数组

引入同余定理

2.java（负数%正数)的结果以及修正

负%正=负->修正 a%p+p，但是假如a是一个正数，那么正数%p然后再加上一个p就变成了多了个p，所以再次%. 也就是说(a%p+p)%p

我们这里求的是前面的x存储了次数，然后看后面的是否有和他相同的，假如有相同的那么就ret表示次数，先从hash里面找前面有没有相同的，然后把前面相同的值加上

假如说前缀和-这个之前的前缀和也可以整除，那么说明a,b可以整除

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
     Map<Integer,Integer> hash=new HashMap<>();
     hash.put(0,1);
     int sum=0;
     int ret=0;
     for(int x:nums){
         //sum是前缀和
         sum+=x;
         //r是表示前缀和的余数
         int r=(sum%k+k)%k;
         ret+=hash.getOrDefault(r,0);
         hash.put(r,hash.getOrDefault(r,0)+1);
     }
 
return ret;
    }
}

力扣525.连续数组

解法:

前缀和+哈希表

1.哈希表里面存什么（因为我们要知道子数组的长度，所以需要用下标来计算长度)

hash<int,int>前缀和，下标

2.什么时候存入哈希表

使用完之后，丢进哈希表

3.如果有重复的<sum,i>怎么办

只保留前面的那一对<sum,i>

4.默认的前缀和为0的情况，如何存储

假如是【0,1】我们改成[-1,1]这时候前缀和是0，我们的长度设置要是-1，他的长度才能是2

hash[0]=-1

5.长度如何计算

 public int findMaxLength(int[] nums) {
        //我们只关心长度，只要下标，才能计算长度
        //一个是前缀和，一个就是下标
        Map<Integer,Integer>hash=new HashMap<>();
        hash.put(0,-1);
        int sum=0;
        int ret=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                sum+=-1;
            }else{
            sum+=1;//计算当前位置前缀和
            }
            //现在前面找一个值也等于sum
            if(hash.containsKey(sum))
            //那么此时的下标，就是我们要找的下标
            ret=Math.max(ret,i-hash.get(sum));
            //看你存不存在当前sum,要是不存在，就放进去即可
            else  hash.put(sum,i);
        }
        return ret;
    }