C++ one pass inspired by @compton_scatter


  • 0
    class Solution {
    public:
        int findMaxLength(vector<int>& nums) {
            int sum = 0, ans = 0;
            unordered_map<int, int> m;
            m[0] = -1;
            for (int i = 0; i < nums.size(); ++i) {
                sum += nums[i];
                int k = 2 * sum - i - 1;
                if (m.count(k)) ans = max(ans, i - m[k]);
                else m[k] = i;
            }
            return ans;
        }
    };
    

    The idea is:
    Let array C be a prefix subarray of nums, separate C into two parts, array A followed by array B, and B is the longest contiguous subarray ending with the last element of C.

    len(A) + len(B) = len(C)
    sum(A) + sum(B) = sum(A) + len(B) / 2 = sum(C)
    // so we have
    2 * sum(C) - len(C) = 2 * sum(A) - len(A)
    

    You can see A and C have the same 2 * sum - len.

    That is to say, if two prefix subarrays A and C of nums have the same 2 * sum - len, we can get len(B) = len(C) - len(A).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.