2022-7-21 剑指offer-前缀和+map

本文主要是介绍2022-7-21 剑指offer-前缀和+map，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         Map<Integer,Integer> map=new HashMap<>();
 4         int n=nums.length,sum=0,ans=0;
 5         int[] pre=new int[n];
 6         for (int i=0;i<n;i++){
 7             sum+=nums[i];
 8             pre[i]=sum;
 9         }
10         for (int i=0;i<n;i++){
11             ans+=map.getOrDefault(pre[i]-k,0);
12             map.put(pre[i],map.getOrDefault(pre[i],0)+1);
13             if (pre[i]==k) ans++;
14         }
15         return ans;
16     }
17 }

思路：先求前缀和，任意两个前缀和的差就是连续的子数组，所以用map记录前缀和的频率，再计算答案。需要注意，如果前缀和本身等于k

,答案要加1。

这篇关于2022-7-21 剑指offer-前缀和+map的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！