leetcode *560. 和为K的子数组
程序员文章站
2022-04-17 13:21:38
...
【题目】*560. 和为K的子数组
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。
【解题思路1】暴力法
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int len = nums.length;
for (int i = 0; i < len; i++) {
int sum = 0;
for (int j = i; j < len; j++) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count;
}
}
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for(int start = 0; start < nums.length; start++){
int sum = 0;
for(int end = start; end >= 0; end--){
sum += nums[end];
if(sum == k){
count++;
}
}
}
return count;
}
}
【解题思路2】前缀和
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k))
count += mp.get(pre - k);
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
下一篇: 560. 和为K的子数组
推荐阅读
-
LeetCode 1 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
leetcode:求两数之和,给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
Leetcode打卡8:题号1:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案
-
LeetCode1.两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,返回数组下标。假设每种输入只对应一个答案。但数组中同一个元素不能使用两遍
-
Leetcode——给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。(java语言)
-
LeetCode [Python]1. 两数之和给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
求数组元素和是K的倍数的子串的最大长度
-
文件夹下(包含子文件夹和文件),取文件夹和子文件夹下所有后缀为JPG的文件的,路径和文件名 ,把路径和文件名放在数组中
-
[LeeCode 862. 和至少为 K 的最短子数组]单调栈
-
LeetCode 907. 子数组的最小值之和--单调栈+闭区间和开区间处理