各个元素之和等于给定值的连续子数组的个数

2021-05-01 10:27

阅读：450

标签：次数 sub int mis 开始 color span private return

给定一个数组arr，给定一个数target。求，各个元素之和等于target的连续子数组的个数，时间复杂度为O(N)，空间复杂度也为O(N)

借助一个Map即可实现。Map中保存的是：从arr的最左侧元素（也就是下标为0的元素）开始，到当前位置为止，所有元素的和出现的次数。

 1 private int getNumOfSubThatSumIsTarget(int[] arr, int target) {
 2     Map map = new HashMap();
 3     map.put(0, 1);
 4     
 5     int result = 0;
 6     int curSum = 0;
 7     for (int i = 0; i i) {
 8         curSum += arr[i];
 9         
10         result += map.getOrDefault(curSum - target, 0);
11         
12         map.put(curSum, map.getOrDefault(curSum, 0) + 1);
13     }
14     
15     return result;
16 }

各个元素之和等于给定值的连续子数组的个数

标签：次数 sub int mis 开始 color span private return

原文地址：https://www.cnblogs.com/adgjl/p/13220323.html

上一篇：了解redis的单线程模型工作原理？一篇文章就够了

下一篇：Java中守护线程和本地线程区别，这特么太重要了！

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：各个元素之和等于给定值的连续子数组的个数
文章链接：http://soscw.com/essay/80818.html

亲，登录后才可以留言！

各个元素之和等于给定值的连续子数组的个数

评论

热门文章

推荐文章

最新文章

置顶文章