22.Contiguous Array

Leetcode.525

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int maxLength = 0;
        vector<int> prefixSum(n+1, 0);
        map<int, int> hash;
        
        hash[0] = 0;
        prefixSum[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
            int n = 2 * prefixSum[i] - i;
            if (hash.find(n) != hash.end()) {
                maxLength = max(maxLength, i - hash[n]);
            } else {
                hash[n] = i;
            }
        }
        
        return maxLength;
    }
};