算法——和为K的连续子数组
2024-08-26 20:33:26
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
链接: leetcode.
解题思路:
- 第一反应回想到双指针的算法,但是数组中的元素有可能为负数,所以,时间复杂度可能是n三方的。
- 然后到利用数组的前缀和,然后二次循环遍历,这样时间复杂都是n方的。
- 其实可以改进上一种算法,将已经遍历过的元素前缀和存到哈希表中,然后在计算之后的总和时,只要查询哈希表中相应值的数量,就能知道这个位置总和为K的数量。
// created by lippon
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
if(n == 0) return 0;
int[] l = new int[n + 1];
int res = 0, sum = 0;
for(int i = 0; i < n; i++) {
sum += nums[i];
l[i + 1] = sum;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i <= n; i++) {
// 查询表中,与当前前缀之差为k的值的个数
if(i > 0 && map.containsKey(l[i] - k)) res += map.get(l[i] - k);
// 再将当前前缀放入表中
map.put(l[i], map.getOrDefault(l[i], 0) + 1);
}
return res;
}
}
最新文章
- BZOJ1598: [Usaco2008 Mar]牛跑步
- 互斥锁(Mutex)
- Android项目实战(十二):解决OOM的一种偷懒又有效的办法
- nmon性能监控工具总结
- Java POI操作Excle工具类
- Careercup - Facebook面试题 - 5733320654585856
- Java was started but returned exit code=13
- 前端知识复习二(js)
- 【LeetCode】152. Maximum Product Subarray
- centos 7 最小安装后 安装FTP服务器 vsftp
- Go开发之路(目录)
- pyinstaller使用错误 SyntaxError: Non-UTF-8 code starting with &#39;\xb4&#39; in file C:......
- JavaScript 删除某个数组中指定的对象
- FILTER——JAVA
- tp5.0 composer命令插件
- linux kernel swap daemon
- [EffectiveC++]item26:尽可能延后变量定义式的出现时间
- WCF学习 (三)深入认识WCF契约
- 我是IT小小鸟读书笔记
- i2c 协议解析