一维前缀和 连续数组和为k
2024-09-07 16:06:27
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
滑动窗口没办法解决有负数的情况
方法一：
预处理 前缀和 sum_ij = preSum[j] - preSum[i-1];
class Solution {
public int subarraySum(int[] nums, int k) {
//滑动窗口没办法解决有负数的情况
//预处理 前缀和 sum_ij = preSum[j] - preSum[i-1];\
int n = nums.length;
int[] preSums = new int[n+1];
for(int i=0;i<n;++i)
{
preSums[i+1] = preSums[i] + nums[i];
}
int ans = 0;
for(int i=1;i<=n;++i)
{
for(int j=0;j<i;++j)
{
if(preSums[i]-preSums[j]==k) ++ans;
}
}
return ans;
}
方法二
使用HashMap，sumToCount的哈希表，其中key值是sum，value是count，sum-k如果有则加上该count
class Solution {
public int subarraySum(int[] nums, int k) {
//滑动窗口没办法解决有负数的情况
//预处理 前缀和 sum_ij = preSum[j] - preSum[i-1];\
// int n = nums.length;
// int[] preSums = new int[n+1];
// for(int i=0;i<n;++i)
// {
// preSums[i+1] = preSums[i] + nums[i];
// }
// int ans = 0;
// for(int i=1;i<=n;++i)
// {
// for(int j=0;j<i;++j)
// {
// if(preSums[i]-preSums[j]==k) ++ans;
// }
// }
// return ans;
//使用map<sum,count>
Map<Integer,Integer> sumCount = new HashMap<>();
sumCount.put(0,1);
int sum = 0;
int count = 0;
for(int num : nums)
{
sum += num;
count += sumCount.getOrDefault(sum-k,0);//取不到就是0
sumCount.put(sum, sumCount.getOrDefault(sum,0)+1);//sum的 次数加1
}
return count;
}
}
最新文章
- elasticsearch完全匹配
- JavaScript 中this与Dom中的注意
- WordPress的have_posts()和the_post()用法解析
- c# 图片XML序列化与反序列化
- VC Dimension -衡量模型与样本的复杂度
- ecshop中404错误页面设置
- 73_leetcode_Construct Binary Tree from Inorder and Postorder Traversal
- Swing-布局管理器之GridLayout（网格布局）-入门
- Debian GNU/Linux 8.4 (jessie)编译安装php.md
- NFS+sersync+Keepalived高可用方案
- DBUtils学习总结
- C# 换行
- 02-CSS&JS
- win10更新后，可以远程桌面ping也没问题，但是无法访问共享文件夹的解决方法
- js 上传文件
- React-Native视频组件react-native-video使用（安卓版）
- 使用通用mapper 生成代码
- [译文]c#扩展方法(Extension Method In C#)
- mini2440裸机试炼之——看门狗中断和复位操作
- 5 属性 property