@@ -0,0 +1,1822 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one,%0A * return 0 instead.%0A * %3Cp%3E%0A * Note:%0A * The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.%0A * %3Cp%3E%0A * Example 1:%0A * Given nums = %5B1, -1, 5, -2, 3%5D, k = 3,%0A * return 4. (because the subarray %5B1, -1, 5, -2%5D sums to 3 and is the longest)%0A * %3Cp%3E%0A * Example 2:%0A * Given nums = %5B-2, -1, 2, 1%5D, k = 1,%0A * return 2. (because the subarray %5B-1, 2%5D sums to 1 and is the longest)%0A * %3Cp%3E%0A * Follow Up:%0A * Can you do it in O(n) time?%0A * %3Cp%3E%0A * Company Tags: Palantir, Facebook%0A * Tags: Hash Table%0A * Similar Problems: (M) Minimum Size Subarray Sum, (E) Range Sum Query - Immutable%0A */%0Apublic class MaximumSizeSubarraySumEqualsk %7B%0A%0A    /**%0A     * For 0 %3C= i %3C j %3C nums.length,%0A     * Find max(i, j) for sum%5Bj%5D - sum%5Bi-1%5D = k.%0A     * Except when i = 0.%0A     * The brute-force way is we loop through the array, keep updating sum.%0A     * Then subtract with each previous sum to see if it's k.%0A     * But previous sum is already calculated, and we can use a map to get it in O(1).%0A     */%0A    public int maxSubArrayLen(int%5B%5D nums, int k) %7B%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        int res = 0;%0A        int sum = 0;%0A        map.put(0, -1); // Sum is 0 for index -1. Make sure sum%5Bj%5D - sum%5Bi-1%5D always works.%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            sum += nums%5Bi%5D;%0A            if (map.containsKey(sum - k)) %7B%0A                res = Math.max(res, i - map.get(sum - k));%0A            %7D%0A            if (!map.containsKey(sum)) %7B // Keep only the smallest i%0A                map.put(sum, i);%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A%0A%7D%0A

add maximum size subarray sum