建一个类似淘宝的网站需要多少钱,园区 网站建设方案,小程序报价单模板,装饰网站建设多少钱给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#xff1a;
输入#xff1a;nums [1,2,3], k…给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。 示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2提示
1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107
读一遍应该就懂了不懂留言或者私信看到第一时间解答
class Solution {/**这个题目竟然有负数所以不符合滑动窗口的条件这个题我们需要用哈希表的解法基本思路就是如果从0~i的累加值是x前面某个位置0~j的累加和中有多少个x-k那以i结尾的子数组就有多少个*/public int subarraySum(int[] nums, int k) {/**边界判断也可以没有 */if(nums.length 1 nums[0] ! k) {return 0;}/**定义一个hashmap用来保存0~j位置的某个累加和出现了多少次 */MapInteger,Integer countMap new HashMap();/**这里一定要放个0的值因为很可能0位置的值就是k */countMap.put(0,1);int preSum 0;/**count用来统计结果数 */int count 0;for(int i 0; i nums.length; i) {/**把当前值加到preSum里 */preSum nums[i];/**当前的累加和是preSum,如果前面出现了preSum-k多少次就有多少个以i位置结尾的子数组的和为k如果没有preSum-k则没有以i位置结尾的子数组满足这个条件这里我们举个例子比如当前的累加和是100然后我们的k是20那我们只需要看一下前面有多少个80就行了这个80是啥呢就是preSum - k */if(countMap.containsKey(preSum - k)) {count countMap.get(preSum - k);}/**不管包含不包含当前的值都要放进去记住用原来的数量或者0 1*/countMap.put(preSum, countMap.getOrDefault(preSum, 0) 1);}return count;}
}
