930. Binary Subarrays With Sum

leetcode medium

#array#csharp#hash-table#leetcode#medium#prefix-sum

Task

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:

Input: nums = [1,0,1,0,1], goal = 2

Output: 4

C# solution

matched/original

using System.Collections.Generic;
public class Solution {
    public int NumSubarraysWithSum(int[] nums, int goal) {
        var prefixSumCount = new Dictionary<int, int>();
        prefixSumCount[0] = 1;
        int currentSum = 0;
        int count = 0;
        
        foreach (int num in nums) {
            currentSum += num;
            if (prefixSumCount.ContainsKey(currentSum - goal)) {
                count += prefixSumCount[currentSum - goal];
            }
            if (prefixSumCount.ContainsKey(currentSum)) {
                prefixSumCount[currentSum]++;
            } else {
                prefixSumCount[currentSum] = 1;
            }
        }
        
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int NumSubarraysWithSum(vector<int>& nums, int goal) {
        var prefixSumCount = new unordered_map<int, int>();
        prefixSumCount[0] = 1;
        int currentSum = 0;
        int count = 0;
        
        foreach (int num in nums) {
            currentSum += num;
            if (prefixSumCount.count(currentSum - goal)) {
                count += prefixSumCount[currentSum - goal];
            }
            if (prefixSumCount.count(currentSum)) {
                prefixSumCount[currentSum]++;
            } else {
                prefixSumCount[currentSum] = 1;
            }
        }
        
        return count;
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            count += prefixSumCount.getOrDefault(currentSum - goal, 0);
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }
}

Python solution

matched/original

def numSubarraysWithSum(nums, goal):
    prefix_sum_count = {0: 1}
    current_sum = 0
    count = 0
    
    for num in nums:
        current_sum += num
        if current_sum - goal in prefix_sum_count:
            count += prefix_sum_count[current_sum - goal]
        if current_sum in prefix_sum_count:
            prefix_sum_count[current_sum] += 1
        else:
            prefix_sum_count[current_sum] = 1
    
    return count

Go solution

matched/original

package main

import "fmt"

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := make(map[int]int)
    prefixSumCount[0] = 1

    currentSum, count := 0, 0

    for _, num := range nums {
        currentSum += num

        if val, exists := prefixSumCount[currentSum-goal]; exists {
            count += val
        }

        prefixSumCount[currentSum]++
    }

    return count
}

func main() {
    nums := []int{1, 0, 1, 0, 1}
    goal := 2
    fmt.Println(numSubarraysWithSum(nums, goal))
}

Explanation

Algorithm

Использовать словарь для хранения количества встреченных сумм префиксов.

Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

Пройти по массиву и обновить текущую сумму.

Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов.

Обновить словарь префиксных сумм.

Вернуть счетчик подмассивов.

😎