Count subarrays with a given sum

def count_subarrays(nums, k):
    counts = {0: 1}          # the empty prefix, so subarrays starting at index 0 are counted
    prefix = total = 0
    for x in nums:
        prefix += x
        total += counts.get(prefix - k, 0)   # look up first...
        counts[prefix] = counts.get(prefix, 0) + 1   # ...then record this prefix
    return total

#include <unordered_map>
#include <vector>
using namespace std;

int solve(vector<int> nums, long long k) {
    unordered_map<long long, int> counts;
    counts[0] = 1;                       // the empty prefix
    long long prefix = 0;
    int total = 0;
    for (int x : nums) {
        prefix += x;
        auto it = counts.find(prefix - k);
        if (it != counts.end()) total += it->second;   // look up first...
        counts[prefix]++;                              // ...then record
    }
    return total;
}

import java.util.*;

class Solution {
    public int countSubarrays(int[] nums, long k) {
        Map<Long, Integer> counts = new HashMap<>();
        counts.put(0L, 1);                   // the empty prefix
        long prefix = 0;
        int total = 0;
        for (int x : nums) {
            prefix += x;
            total += counts.getOrDefault(prefix - k, 0);          // look up first...
            counts.merge(prefix, 1, Integer::sum);                // ...then record
        }
        return total;
    }
}

function countSubarrays(nums, k) {
  const counts = new Map([[0, 1]]);   // the empty prefix
  let prefix = 0, total = 0;
  for (const x of nums) {
    prefix += x;
    total += counts.get(prefix - k) || 0;          // look up first...
    counts.set(prefix, (counts.get(prefix) || 0) + 1);   // ...then record
  }
  return total;
}

use std::collections::HashMap;

fn solve(nums: &[i32], k: i64) -> i32 {
    let mut counts: HashMap<i64, i32> = HashMap::new();
    counts.insert(0, 1);                 // the empty prefix
    let mut prefix: i64 = 0;
    let mut total = 0;
    for &x in nums {
        prefix += x as i64;
        total += *counts.get(&(prefix - k)).unwrap_or(&0);   // look up first...
        *counts.entry(prefix).or_insert(0) += 1;             // ...then record
    }
    total
}

import qualified Data.Map.Strict as M
import Data.List (scanl')

solve :: [Int] -> Int -> Int
solve xs k = go (M.singleton 0 1) 0 (scanl' (+) 0 xs)
  where
    -- walk the prefix sums, counting how many earlier prefixes equal (p - k)
    go _ acc []       = acc
    go _ acc [_]      = acc
    go m acc (_:p:ps) =
      let hit = M.findWithDefault 0 (p - k) m
          m'  = M.insertWith (+) p 1 m
      in go m' (acc + hit) (p:ps)