525.连续数组

链接：525.连续数组
难度：Medium
标签：数组、哈希表、前缀和
简介：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

题解 1 - typescript

• 编辑时间：2021-06-03
• 执行用时：144ms
• 内存消耗：46.8MB
• 编程语言：typescript
• 解法介绍：把 0 都置-1,利用前缀和判断和为 0 的值。

function findMaxLength(nums: number[]): number {
  const len = nums.length;
  for (let i = 0; i < len; i++) if (nums[i] === 0) nums[i] = -1;
  let sum = 0;
  let ans = 0;
  const map = new Map<number, number>([[0, -1]]);
  for (let i = 0; i < len; i++) {
    sum += nums[i];
    let prev = map.get(sum);
    if (prev !== undefined) ans = Math.max(ans, i - prev);
    else map.set(sum, i);
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2021-12-23
• 执行用时：116ms
• 内存消耗：81.8MB
• 编程语言：cpp
• 解法介绍：前缀和。

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