力扣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即可。
