Share my o(n) solution for max SubArray sum Length


  • 3
    L
        public int maxSubArrayLen(int[] nums, int k) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
    // the affix sum matrix would be used to store the sum from index 0 to any index. In this way the subsum of    // the array between i and j is simply subSum[j] - subSum[i-1];
            // use a hashmap to store the sub sum from index 0 to index i for the quick reference.
            long[] subSum = new long[nums.length+1];
            int maxLen = 0;
            HashMap<Long, Integer> hashedSum = new HashMap<>();
            hashedSum.put(0L, 0);
            for (int i = 1; i < subSum.length; ++i) {
                subSum[i] = subSum[i-1] + nums[i-1];
                if (hashedSum.containsKey(subSum[i] - k)) {
                    maxLen = Math.max(i - hashedSum.get(subSum[i] - k), maxLen);
                }
                if (!hashedSum.containsKey(subSum[i])) {
                    // only keep the first subSum. In this way, only the longest subarray will be guaranteed.
                    hashedSum.put(subSum[i], i);
                }
            }
            return maxLen;
        }

Log in to reply
 

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