class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
}
};
930. 和相同的二元子数组
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
示例 1：
输入：nums = [1,0,1,0,1], goal = 2 输出：4 解释： 有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
示例 2：
输入：nums = [0,0,0,0,0], goal = 0 输出：15
提示：
1 <= nums.length <= 3 * 104nums[i] 不是 0 就是 10 <= goal <= nums.length原站题解
javascript 解法, 执行用时: 60 ms, 内存消耗: 42.9 MB, 提交时间: 2022-12-10 23:20:49
/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var numSubarraysWithSum = function(nums, goal) {
const n = nums.length;
let left1 = 0, left2 = 0, right = 0;
let sum1 = 0, sum2 = 0;
let ret = 0;
while (right < n) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1];
left1++;
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2];
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
};
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2022-12-10 23:20:38
func numSubarraysWithSum(nums []int, goal int) (ans int) {
left1, left2 := 0, 0
sum1, sum2 := 0, 0
for right, num := range nums {
sum1 += num
for left1 <= right && sum1 > goal {
sum1 -= nums[left1]
left1++
}
sum2 += num
for left2 <= right && sum2 >= goal {
sum2 -= nums[left2]
left2++
}
ans += left2 - left1
}
return
}
java 解法, 执行用时: 2 ms, 内存消耗: 44.9 MB, 提交时间: 2022-12-10 23:20:25
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int n = nums.length;
int left1 = 0, left2 = 0, right = 0;
int sum1 = 0, sum2 = 0;
int ret = 0;
while (right < n) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1];
left1++;
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2];
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
}
}
cpp 解法, 执行用时: 16 ms, 内存消耗: 28.2 MB, 提交时间: 2022-12-10 23:20:12
// 滑动窗口
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int n = nums.size();
int left1 = 0, left2 = 0, right = 0;
int sum1 = 0, sum2 = 0;
int ret = 0;
while (right < n) {
sum1 += nums[right];
while (left1 <= right && sum1 > goal) {
sum1 -= nums[left1];
left1++;
}
sum2 += nums[right];
while (left2 <= right && sum2 >= goal) {
sum2 -= nums[left2];
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
}
};
javascript 解法, 执行用时: 68 ms, 内存消耗: 47.3 MB, 提交时间: 2022-12-10 23:19:47
/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var numSubarraysWithSum = function(nums, goal) {
let sum = 0;
const cnt = new Map();
let ret = 0;
for (const num of nums) {
cnt.set(sum, (cnt.get(sum) || 0) + 1);
sum += num;
ret += cnt.get(sum - goal) || 0;
}
return ret;
};
golang 解法, 执行用时: 28 ms, 内存消耗: 9 MB, 提交时间: 2022-12-10 23:19:34
func numSubarraysWithSum(nums []int, goal int) (ans int) {
cnt := map[int]int{}
sum := 0
for _, num := range nums {
cnt[sum]++
sum += num
ans += cnt[sum-goal]
}
return
}
java 解法, 执行用时: 20 ms, 内存消耗: 46.4 MB, 提交时间: 2022-12-10 23:19:16
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int sum = 0;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
int ret = 0;
for (int num : nums) {
cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
sum += num;
ret += cnt.getOrDefault(sum - goal, 0);
}
return ret;
}
}
cpp 解法, 执行用时: 68 ms, 内存消耗: 35.5 MB, 提交时间: 2022-12-10 23:19:04
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int sum = 0;
unordered_map<int, int> cnt;
int ret = 0;
for (auto& num : nums) {
cnt[sum]++;
sum += num;
ret += cnt[sum - goal];
}
return ret;
}
};