leetcode560 和为k的子数组
package java2024_10.day30;
import java.util.HashMap;
public class leetcode560 {
/*思路:前缀和+哈希表
a[j]-a[i]=k
即a[i]=a[j]-k
遍历到下标j的时候,先判a[j]==k,相等就ans++,然后查哈希表中a[j]-k的数的个数,然后把a[j]放入哈希表中
相当于:
1.查j前缀和是否等于K
2.查哈希表是否有前缀和j-i等于k
3.将j前缀和加入到哈希表中
*/
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<>();
int ans=0,m;
int len=nums.length;
int[] a=new int[len+1];
a[0]=nums[0];
map.put(a[0],1);
if(a[0]==k) ans++;
for (int i = 1; i < len; i++) {
a[i]=a[i-1]+nums[i];
m=a[i];
if (m==k) ans++;
ans+=map.getOrDefault(m-k,0);
map.put(m,map.getOrDefault(m,0)+1);
}//a数组储存前缀和
return ans;
}
}
标签:map,leetcode560,数组,nums,int,哈希,ans,前缀
From: https://www.cnblogs.com/vastjoy/p/18517671