C#: Easy to understand O(n) Solution with Explanation. (Accepted)


  • 0

    0_1523421094972_73ee34db-901c-48f0-9281-a53f6a305cf6-image.png
    Time Complexity: O(n).
    Basic Idea:

    • The runningSumToIndexMap stores the sum of all elements before index i (inclusive) as key, and i as value.
    • For each i, check the runningSum and also runningSum - k to see if there is any that equals k, and update maxSubArrayLen.
    public class Solution {
        public int MaxSubArrayLen(int[] nums, int k) {
            int maxSubArrayLen = 0;
            int runningSum = 0;
            Dictionary<int, int> runningSumToIndexMap = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++) {
                runningSum += nums[i];
                if (runningSum == k)
                    maxSubArrayLen = i + 1;
                else {
                    int val = 0;
                    if (runningSumToIndexMap.TryGetValue(runningSum - k, out val))
                        maxSubArrayLen = Math.Max(maxSubArrayLen, i - val);
                }
    
                if (!runningSumToIndexMap.ContainsKey(runningSum))  //Since we want the index as left as possible, only store 1st duplicate.
                    runningSumToIndexMap[runningSum] = i;
            }
            return maxSubArrayLen;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.