Python dict C++陣列Prefix Sum解Leetcode 525 Contiguous Array

Python  dict C++陣列Prefix Sum解Leetcode 525 Contiguous Array

使用 Prefix sum 來計算 n0 中的 0 和 n1 中的 1。 使用容器記錄n1-n0的索引。

hash表 (C++ unordered_map, Python dict) 用於此任務。

第二種方法是從第一種方法修改而來的陣列版本，速度很快。python這有提供。

---

Use Prefix sum to count 0s in n0 & 1s in n1. Use a container to record the index for n1-n0.

A hash table (C++ unordered_map, Python dict) is used for this task.

2nd approach is an array version modified from the 1st one which is fast.

[codes on Leetcode]https://leetcode.com/problems/contiguous-array/solutions/4881438/prefix-sum-hash-table-array-31ms-beats-100/

[Leetcode playList]https://www.youtube.com/watch?v=WjrWkPysfRM&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

[Dynamic Programming Playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        n=len(nums)
        n1=0
        n0=0
        maxLen=0
        mp={}
        mp[0]=-1
        for i in range(n):
            n1+=nums[i]
            n0=(i+1)-n1
            if (n1-n0) in mp:
                maxLen=max(maxLen, i-mp[n1-n0])
            else:
                mp[n1-n0]=i
        return maxLen