【LeeCode】930. 和相同的二元子数组

【题目描述】

给你一个二元数组 ​​nums​​​ ，和一个整数 ​​goal​​​ ，请你统计并返回有多少个和为 ​​goal​​ 的 非空 子数组。

子数组 是数组的一段连续部分。

 ​​https://leetcode.cn/problems/binary-subarrays-with-sum/​​

【示例】

【代码】admin

枚举，参考  ​​560. 和为 K 的子数组​​

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int len = nums.length;
int sum = 0;
int count = 0;

for (int i = 0; i < len; i++){
for (int j = i; j < len; j++){
sum += nums[j];
if (sum == goal){
count++;
                }
            }
sum = 0;
        }
System.out.println(count);
return count;
    }
}

public class Test {
public static void main(String[] args) {
new Solution().numSubarraysWithSum(new int[] {1,0,1,0,1}, 2); // 输出：4
new Solution().numSubarraysWithSum(new int[] {0,0,0,0,0}, 0); // 输出: 15
    }
}

【代码】前缀和

参考  ​​560. 和为 K 的子数组   会超时​​

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int len = nums.length;
int count = 0;
int[] presum = new int[len + 1];
for (int i = 0; i < len; i++){
presum[i + 1] = presum[i] + nums[i];
        }

for (int i = 0; i < len; i++){
for (int j = i; j < len; j++){
if (presum[j + 1] - presum[i] == goal){
count++;
                }
            }
        }
// System.out.println(count);
return count;
    }
}

public class Test {
public static void main(String[] args) {
new Solution().numSubarraysWithSum(new int[] {1,0,1,0,1}, 2); // 输出：4
new Solution().numSubarraysWithSum(new int[] {0,0,0,0,0}, 0); // 输出: 15
    }
}

【代码】前缀和 + Hash

​​560. 和为 K 的子数组 ​​

package com.company;
import java.util.*;

// 2022-02-13
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
if (nums.length == 0) return 0;
Map<Integer, Integer> map = new HashMap<>();
// 预存前缀和为 0 的情况
map.put(0, 1);
int count = 0;
int presum = 0;

for (int x : nums){
presum += x;
if (map.containsKey(presum - x)){
count += map.get(presum - x);
           }
map.put(presum, map.getOrDefault(presum, 0) + 1);
       }
return count;
    }
}

public class Test {
public static void main(String[] args) {
new Solution().numSubarraysWithSum(new int[] {1,0,1,0,1}, 2); // 输出：4
new Solution().numSubarraysWithSum(new int[] {0,0,0,0,0}, 0); // 输出: 15
    }
}