Prefix Sums

def subarray_sum(nums: list[int], k: int) -> int:
    """Number of contiguous subarrays of `nums` whose values add up to `k`."""
    # How many times each prefix sum has appeared so far. The empty prefix
    # (sum 0) counts once, so subarrays that start at index 0 are found too.
    seen = {0: 1}
    running = 0
    count = 0
    for num in nums:
        running += num
        # Every earlier prefix equal to running - k starts a subarray summing to k.
        # Look it up before recording running, or k = 0 would match itself.
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count


if __name__ == "__main__":
    print(subarray_sum([1, 1, 1], 2))  # 2
    print(subarray_sum([1, 2, 3], 3))  # 2
    print(subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7))  # 4
    print(subarray_sum([1, -1, 0], 0))  # 3

// Number of contiguous subarrays of `nums` whose values add up to `k`.
export function subarraySum(nums: number[], k: number): number {
  // How many times each prefix sum has appeared so far. The empty prefix
  // (sum 0) counts once, so subarrays that start at index 0 are found too.
  const seen = new Map<number, number>([[0, 1]]);
  let running = 0;
  let count = 0;
  for (const num of nums) {
    running += num;
    // Every earlier prefix equal to running - k starts a subarray summing to k.
    // Look it up before recording running, or k = 0 would match itself.
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}

console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2
console.log(subarraySum([3, 4, 7, 2, -3, 1, 4, 2], 7)); // 4
console.log(subarraySum([1, -1, 0], 0)); // 3

package main

import "fmt"

// subarraySum returns the number of contiguous subarrays of nums whose values
// add up to k.
func subarraySum(nums []int, k int) int {
	// How many times each prefix sum has appeared so far. The empty prefix
	// (sum 0) counts once, so subarrays that start at index 0 are found too.
	seen := map[int]int{0: 1}
	running := 0
	count := 0
	for _, num := range nums {
		running += num
		// Every earlier prefix equal to running - k starts a subarray summing to k.
		// Look it up before recording running, or k = 0 would match itself.
		count += seen[running-k]
		seen[running]++
	}
	return count
}

func main() {
	fmt.Println(subarraySum([]int{1, 1, 1}, 2))                 // 2
	fmt.Println(subarraySum([]int{1, 2, 3}, 3))                 // 2
	fmt.Println(subarraySum([]int{3, 4, 7, 2, -3, 1, 4, 2}, 7)) // 4
	fmt.Println(subarraySum([]int{1, -1, 0}, 0))                // 3
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Number of contiguous subarrays of nums whose values add up to k.
    public static int SubarraySum(int[] nums, int k)
    {
        // How many times each prefix sum has appeared so far. The empty prefix
        // (sum 0) counts once, so subarrays that start at index 0 are found too.
        var seen = new Dictionary<int, int> { [0] = 1 };
        int running = 0, count = 0;
        foreach (int num in nums)
        {
            running += num;
            // Every earlier prefix equal to running - k starts a subarray summing to k.
            // Look it up before recording running, or k = 0 would match itself.
            count += seen.GetValueOrDefault(running - k);
            seen[running] = seen.GetValueOrDefault(running) + 1;
        }
        return count;
    }

    public static void Main()
    {
        Console.WriteLine(SubarraySum(new[] { 1, 1, 1 }, 2)); // 2
        Console.WriteLine(SubarraySum(new[] { 1, 2, 3 }, 3)); // 2
        Console.WriteLine(SubarraySum(new[] { 3, 4, 7, 2, -3, 1, 4, 2 }, 7)); // 4
        Console.WriteLine(SubarraySum(new[] { 1, -1, 0 }, 0)); // 3
    }
}

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

public class Solution {
    // Number of contiguous subarrays of nums whose values add up to k.
    static int subarraySum(int[] nums, int k) {
        // How many times each prefix sum has appeared so far. The empty prefix
        // (sum 0) counts once, so subarrays that start at index 0 are found too.
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);
        int running = 0, count = 0;
        for (int num : nums) {
            running += num;
            // Every earlier prefix equal to running - k starts a subarray summing to k.
            // Look it up before recording running, or k = 0 would match itself.
            count += seen.getOrDefault(running - k, 0);
            seen.merge(running, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(subarraySum(new int[] {1, 1, 1}, 2)); // 2
        System.out.println(subarraySum(new int[] {1, 2, 3}, 3)); // 2
        System.out.println(subarraySum(new int[] {3, 4, 7, 2, -3, 1, 4, 2}, 7)); // 4
        System.out.println(subarraySum(new int[] {1, -1, 0}, 0)); // 3
    }
}

def product_except_self(nums: list[int]) -> list[int]:
    """answer[i] is the product of every value in `nums` except nums[i], with no division."""
    answer = [1] * len(nums)
    # Forward pass: answer[i] gets the product of everything left of i.
    prefix = 1
    for i in range(len(nums)):
        answer[i] = prefix
        prefix *= nums[i]
    # Backward pass: multiply in the product of everything right of i.
    suffix = 1
    for i in range(len(nums) - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    return answer


if __name__ == "__main__":
    print(product_except_self([1, 2, 3, 4]))  # [24, 12, 8, 6]
    print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]
    print(product_except_self([5, 2]))  # [2, 5]

// answer[i] is the product of every value in `nums` except nums[i], with no division.
export function productExceptSelf(nums: number[]): number[] {
  const answer = new Array<number>(nums.length);
  // Forward pass: answer[i] gets the product of everything left of i.
  let prefix = 1;
  for (let i = 0; i < nums.length; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }
  // Backward pass: multiply in the product of everything right of i.
  let suffix = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer;
}

console.log(JSON.stringify(productExceptSelf([1, 2, 3, 4]))); // [24,12,8,6]
console.log(JSON.stringify(productExceptSelf([-1, 1, 0, -3, 3]))); // [0,0,9,0,0]
console.log(JSON.stringify(productExceptSelf([5, 2]))); // [2,5]

package main

import "fmt"

// productExceptSelf returns answer, where answer[i] is the product of every
// value in nums except nums[i], with no division.
func productExceptSelf(nums []int) []int {
	answer := make([]int, len(nums))
	// Forward pass: answer[i] gets the product of everything left of i.
	prefix := 1
	for i := 0; i < len(nums); i++ {
		answer[i] = prefix
		prefix *= nums[i]
	}
	// Backward pass: multiply in the product of everything right of i.
	suffix := 1
	for i := len(nums) - 1; i >= 0; i-- {
		answer[i] *= suffix
		suffix *= nums[i]
	}
	return answer
}

func main() {
	fmt.Println(productExceptSelf([]int{1, 2, 3, 4}))      // [24 12 8 6]
	fmt.Println(productExceptSelf([]int{-1, 1, 0, -3, 3})) // [0 0 9 0 0]
	fmt.Println(productExceptSelf([]int{5, 2}))            // [2 5]
}

using System;

public class Solution
{
    // answer[i] is the product of every value in nums except nums[i], with no division.
    public static int[] ProductExceptSelf(int[] nums)
    {
        var answer = new int[nums.Length];
        // Forward pass: answer[i] gets the product of everything left of i.
        int prefix = 1;
        for (int i = 0; i < nums.Length; i++)
        {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        // Backward pass: multiply in the product of everything right of i.
        int suffix = 1;
        for (int i = nums.Length - 1; i >= 0; i--)
        {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }

    public static void Main()
    {
        Console.WriteLine(Format(ProductExceptSelf(new[] { 1, 2, 3, 4 }))); // [24, 12, 8, 6]
        Console.WriteLine(Format(ProductExceptSelf(new[] { -1, 1, 0, -3, 3 }))); // [0, 0, 9, 0, 0]
        Console.WriteLine(Format(ProductExceptSelf(new[] { 5, 2 }))); // [2, 5]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}

import java.util.Arrays;

public class Solution {
    // answer[i] is the product of every value in nums except nums[i], with no division.
    static int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];
        // Forward pass: answer[i] gets the product of everything left of i.
        int prefix = 1;
        for (int i = 0; i < nums.length; i++) {
            answer[i] = prefix;
            prefix *= nums[i];
        }
        // Backward pass: multiply in the product of everything right of i.
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            answer[i] *= suffix;
            suffix *= nums[i];
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(productExceptSelf(new int[] {1, 2, 3, 4}))); // [24, 12, 8, 6]
        System.out.println(Arrays.toString(productExceptSelf(new int[] {-1, 1, 0, -3, 3}))); // [0, 0, 9, 0, 0]
        System.out.println(Arrays.toString(productExceptSelf(new int[] {5, 2}))); // [2, 5]
    }
}