Subarray Sum K

Medium

Python

def subarray_sum(nums,k):
    count=total=0; prefix={0:1}
    for n in nums:
        total+=n
        count+=prefix.get(total-k,0)
        prefix[total]=prefix.get(total,0)+1
    return count

Java

public int subarraySum(int[] nums,int k){
    int count=0,total=0;
    Map<Integer,Integer> pre=new HashMap<>(); pre.put(0,1);
    for(int n:nums){
        total+=n;
        count+=pre.getOrDefault(total-k,0);
        pre.put(total,pre.getOrDefault(total,0)+1);
    } return count;
}

Key Insight

dict.get() and getOrDefault() equivalent.

Python → Java Differences

dict.get(k,0) vs getOrDefault()
Python {0:1} vs put(0,1)
Prefix sum identical

Python

def subarray_sum(nums,k):
    count=total=0; prefix={0:1}
    for n in nums:
        total+=n
        count+=prefix.get(total-k,0)
        prefix[total]=prefix.get(total,0)+1
    return count

Java

public int subarraySum(int[] nums,int k){
    int count=0,total=0;
    Map<Integer,Integer> pre=new HashMap<>(); pre.put(0,1);
    for(int n:nums){
        total+=n;
        count+=pre.getOrDefault(total-k,0);
        pre.put(total,pre.getOrDefault(total,0)+1);
    } return count;
}

Algorithm Steps

1. Track prefix sums
2. Check sum-k exists

← Previous All Arrays Next →