php的网站架构建设框架,建设网站模板免费,咸阳住房和城乡建设局网站,wordpress菜单变英文给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2 输出#xff1a;2
示例 2#xff1a;
输入#xff1a;nums [1,2,3]…给你一个整数数组 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 1071.暴力解法
class Solution {public int subarraySum(int[] nums, int k) {int sum 0;for (int i 0; i nums.length; i) {int sumi nums[i];if(sumi k) {sum;}for (int j i 1; j nums.length; j) {sumi nums[j];if(sumi k) {sum;}}}return sum;}
}执行用时分布 1594ms 击败26.39%使用 Java 的用户 消耗内存分布 45.40MB 击败22.08%使用 Java 的用户
2.前缀和
class Solution {public int subarraySum(int[] nums, int k) {// 第一种方法的问题在于太多重复计算// 换一个思路如果从第i个数到第j个数这j-i1个数组成的子数组之和为k// 也就是数组nums的前j个数之和 减去 数组nums的前i个数之和 等于 k// 所以可以先统计出来 前N个数之和也就是 《前缀和》这样就可以大幅度减少计算量// 注意前面加了一个 0这样便于处理第0位数的情况看下面例子// 对于 [3,1,2], k 3 而言计算前缀和后转成了[0, 3, 4, 6]// 就可以发现3-03 6-33就有两组子数组满足条件int[] preSum new int[nums.length 1];preSum[0] 0;for (int i 0; i nums.length; i) {preSum[i1] nums[i] preSum[i];}// 还是硬扫但采用从后往前遍历即指定了上面提到的j往前找一个i使得preSum[j] - preSum[i] k其中j iint count 0;for (int j 1; j preSum.length; j) {int target preSum[j] - k;for (int i j - 1; i 0; i--) {if (preSum[i] target) {count;}}}return count;}
}执行用时分布 1110ms 击败41.83%使用 Java 的用户 消耗内存分布 44.56MB 击败67.42%使用 Java 的用户
