前缀和第二弹

力扣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;
    }

力扣1314.矩阵区域和

是一个上面加上一个左边，但是上面和左边都包括你的斜上方，所以减去一个斜上方，再去加上当前位置的数值。

我们该如何求出我们想要的那个点的值呢

首先我们先把我们想要的区域找好

下标映射关系:

为了方便处理边界情况 我们二维dp都是从1开始计数，但是我们的mat是从0开始计数

所以我们，需要多加一列dp[m+1][n+1]

当我门dp表想填写[i][j]->mat[i-1][j-1],当我们使用dp表的时候，填写ret，使用x1,x2的时候，应该x+1,y+1的位置，修改方式，我们求矩阵下标x1,x2的时候+1即可。