325. Maximum Size Subarray Sum Equals k

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/description/

Given an arraynumsand a target valuek, find the maximum length of a subarray that sums tok. If there isn't one, return 0 instead.

Note: The sum of the entirenumsarray is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Givennums=[1, -1, 5, -2, 3],k=3, return4. (because the subarray[1, -1, 5, -2]sums to 3 and is the longest)

Example 2:

Givennums=[-2, -1, 2, 1],k=1, return2. (because the subarray[-1, 2]sums to 1 and is the longest)

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

Thoughts

数组上和为k的子数组最长长度。找和为k的子数组，presum。

Code

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        const int N = nums.size();
        unordered_map<int, int> presum;
        int res = 0;
        presum[0] = -1;
        for (int i = 0, sum = 0; i < N; ++i) {
            sum += nums[i];
            if (presum.count(sum - k)) res = max(res, i - presum[sum - k]);
            if (!presum.count(sum)) presum[sum] = i;
        }
        return res;
    }
};

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

            if (!pos.containsKey(preSum)) {
                pos.put(preSum, i + 1);
            }
        }
        return maxLen;
    }
}

Analysis

做题耗时: 19 min Errors: 1. 还考虑了 pos.containsKey(preSum + k), 对应着sum(i, j) == -k , 不用考虑.

时间O(n), 空间O(n)