Leetcode discuss: 325. Maximum Size Subarray Sum Equals k

 Here is the link. 

First practice - C# - prefix sum - exclusive

Dec. 22, 2020
It takes O(N) time to find maximum size subarray sum equals k using prefix sum to calculate subarray's sum, whereas N is the length of the array.

I used to have problem to define prefix sum, so this time I chose the tip to define (0, 0) as first value, 0 is value of prefix sum, index 0 is exclusive.

Case study
Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Prefix sum is calculated and defined in the following way:
prefixSum[0] - 0, not include any element in the array.
prefixSum[1] - sum of nums[0], exclusive 1 itself.
So for any subarray it will take O(1) to calculate the sum. For example, subarray from [i, j], prefix sum's start index should be i, end index is j + 1, so prefixSum[j + 1] - prefixSum[i] is the subarray's sum. It will take O(1).

All preprocess of prefixSum array takes O(N) time.

public class Solution {
    public int MaxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.Length == 0)
            return 0; 
        
        var map = new Dictionary<int, int>();
        map.Add(0, 0); // exclude index = 0
        
        var prefixSum = 0; 
        var length = nums.Length; 
        var max = 0;
        for(int i = 0; i < length; i++)
        {
            prefixSum += nums[i];
            var target = prefixSum - k;
            if(map.ContainsKey(target))
            {
                var span = i + 1 - map[target];
                max = span > max? span : max; 
            }
            
            if(!map.ContainsKey(prefixSum))
            {
                map.Add(prefixSum, i + 1); // exclusive i + 1
            }
        }
        
        return max; 
    }
}