Question

Formatted question description: https://leetcode.ca/all/325.html

 325 Maximum Size Subarray Sum Equals k

 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, return 0 instead.

 Example 1:

 Given nums = [1, -1, 5, -2, 3], k = 3,
 return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

 Example 2:

 Given nums = [-2, -1, 2, 1], k = 1,
 return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

 Follow Up:
    Can you do it in O(n) time?

 @tag-array

Algorithm

Need to use hash table and cumulative sum, then the benefit of establishing cumulative sum is obvious, if the current cumulative sum is exactly equal to k, then the sub-array from the beginning to this position is a satisfactory solution, but not necessarily the longest Sub-array, and use a hash table to establish the mapping between the cumulative sum and its coordinates, we analyze from the example given in the title:

nums: [1, -1, 5, -2, 3], k = 3

sums: [1, 0, 5, 3, 6]

We can see that the fourth number of the cumulative sum is 3, which is the same as k, which means that the first four numbers are a sub-array that meets the meaning of the question. Let’s look at the second example:

nums: [-2, -1, 2, 1], k = 1

sums: [-2, -3, -1, 0]

We find that no number in the cumulative sum is equal to k, but we know that the answer to this example is [-1, 2], then we look at the first and third numbers of the cumulative sum array, can we see some rules, no Wrong, the third number -1 is subtracted from k to get the first number. This is the law. This is also the method of accumulating and summing the interval. However, there may be repeated numbers in the accumulative sum array, and the key of the hash table The characters cannot be the same, such as the following example:

nums: [1, 0, -1], k = -1

sums: [1, 1, 0]

We found that the first and second numbers of the cumulative sum array are both 1, so how to create a mapping? What I think is to store them in a one-dimensional array, and then compare the first one in the array when comparing Number, when we build the hash table, we start to traverse the hash table. When the cumulative sum is the same as k, we update res. If it is not the same, we check whether the value obtained by subtracting k from the current value is stored in the hash table. Exist, update the result if it exists.

Code

import java.util.HashMap;

public class Maximum_Size_Subarray_Sum_Equals_k {

    public static void main(String[] args) {
        Maximum_Size_Subarray_Sum_Equals_k out = new Maximum_Size_Subarray_Sum_Equals_k();
        Solution s = out.new Solution();

//        System.out.println(s.maxSubArrayLen(new int[]{1, -1, 5, -2, 3}, 3));
        System.out.println(s.maxSubArrayLen(new int[]{1, 0, -1}, -1)); // sums: [1, 1, 0]
    }

    public class Solution {


        public int maxSubArrayLen(int[] nums, int k) {

            // from sum[i] => i index i
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

            int max = 0;
            int sum = 0;

            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];

                if (sum == k) {
                    max = Math.max(max, i + 1);
                }

                int diff = sum - k;

                if (map.containsKey(diff)) {
                    max = Math.max(max, i - map.get(diff));
                }

                if (!map.containsKey(sum)) { // @note: only record the first appearance
                    map.put(sum, i);
                }
            }

            return max;
        }
    }
}

############

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0, -1);
        int s = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i];
            if (mp.containsKey(s - k)) {
                ans = Math.max(ans, i - mp.get(s - k));
            }
            if (!mp.containsKey(s)) {
                mp.put(s, i);
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxSubArrayLen(vector<int>& A, int k) {
        unordered_map<int, int> m{ {0,-1} }; // prefix sum -> first index
        int ans = 0;
        for (int i = 0, sum = 0; i < A.size(); ++i) {
            sum += A[i];
            int target = sum - k;
            if (m.count(target)) ans = max(ans, i - m[target]);
            if (m.count(sum) == 0) m[sum] = i;
        }
        return ans;
    }
};

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        mp = {0: -1}
        s = ans = 0
        for i, v in enumerate(nums):
            s += v
            if s - k in mp:
                ans = max(ans, i - mp[s - k])
            if s not in mp:
                mp[s] = i
        return ans

############

class Solution(object):
  def maxSubArrayLen(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    d = {0: -1}
    maxLen = 0
    _sum = 0
    for i in range(0, len(nums)):
      _sum += nums[i]
      if _sum not in d:
        d[_sum] = i
      if _sum - k in d:
        maxLen = max(maxLen, i - d[_sum - k])
    return maxLen

func maxSubArrayLen(nums []int, k int) int {
	mp := map[int]int{0: -1}
	s, ans := 0, 0
	for i, v := range nums {
		s += v
		if j, ok := mp[s-k]; ok {
			ans = max(ans, i-j)
		}
		if _, ok := mp[s]; !ok {
			mp[s] = i
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

325 - Maximum Size Subarray Sum Equals k

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions