2022-7-21 剑指offer-前缀和+map
2022/7/22 6:59:46
本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?