东莞手机网站建设公司,展厅设计公司招聘,手工做刀网站,微网站如何建立1 和为K的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a;
输入#xff1…1 和为K的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2
方法一
暴力枚举但是运行是出现问题【不清楚为何运行不通过 — 原因子数组为下标连续】
class Solution {public int subarraySum(int[] nums, int k) {// 方法一暴力枚举// 计数 用于返回和为K的子数组个数int count 0;// 遍历数组for(int i 0 ; i nums.length; i){for(int j i 1; j nums.length; j){if(nums[i] nums[j] k){count;}}}return count;}
} 修改 之后代码:
class Solution {public int subarraySum(int[] nums, int k) {// 方法一暴力枚举// 计数 用于返回和为K的子数组个数int count 0;// 遍历数组for(int i 0 ; i nums.length; i){int sum 0;for(int j i ; j nums.length; j){sum sum nums[j];if(sum k){count;}}}return count;}
}
方法二
前缀和 public static int subarrySum(int[] nums, int k){// 定义计数 用于返回最终结果int count 0;// 定义哈希表 用于记录前缀和 和 出现的次数 key - valueMapInteger, Integer preSum new HashMap();// 初始化前缀和 0 出现的次数为1preSum.put(0, 1);// 记录当前的前缀和(当前位置之前的元素和)int currSum 0;// 遍历数组for (int i 0; i nums.length; i) {// 更新前缀和currSum currSum nums[i];// 如果存在前缀和为 k - currSum则说明存在和为K的子数组if(preSum.containsKey( currSum - k)){// 更新计数count count preSum.get(currSum - k);}// 更新哈希表 即更新前缀和以及出现的次数preSum.put(currSum, preSum.getOrDefault(currSum, 0) 1);}return count;}
