Mind palace

some thoughts

0%

325. Maximum Size Subarray Sum Equals k

Posted on Edited on In Disqus:
Symbols count in article: 839 Reading time ≈ 1 mins.

O(n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> m{{0, -1}}; // 注意要初始化0的下标为-1
        int n = nums.size();
        int res = 0;
        for (int i = 0, sum = 0; i < n; ++i) {
            sum += nums[i];
            int t = sum - k;
            if (m.count(t)) {
                res = max(res, i - m[t]);
            }
            m[sum] = m.count(sum) ? m[sum] : i;
        }
        return res;
    }
};

O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> presum(n + 1);
        unordered_map<int, int> m{{0, 0}};
        for (int i = 1; i <= n; ++i) {
            presum[i] = presum[i - 1] + nums[i - 1];
            m[presum[i]] = max(m[presum[i]], i);
        }
        int res = 0;
        for (int i = 0; i <= n; ++i) {
            int t = presum[i] + k;
            if (m.count(t)) {
                res = max(res, m[t] - i);
            }
        }
        return res;
    }
};