1. 題目

給定一個二進制數(shù)組, 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組（的長度）。

示例 1: 輸入: [0,1] 輸出: 2 說明: [0, 1] 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。示例 2: 輸入: [0,1,0] 輸出: 2 說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。 來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/contiguous-array 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：
LeetCode 560. 和為K的子數(shù)組（前綴和差分）
LeetCode 1248. 統(tǒng)計「優(yōu)美子數(shù)組」（要復習）

• 把0看成-1，找和為0的最長長度，跟560題差不多
• 記錄前綴和，第一次出現(xiàn)時，存入map，記錄下標
• 第二次出現(xiàn)時，做差，中間的長度就是和為0的區(qū)間

class Solution { public:int findMaxLength(vector<int>& nums) {int i, n = nums.size(), sum = 0, maxlen = 0;unordered_map<int,int> m;//sum, 第一次出現(xiàn)sum時的idxm[0] = -1;for(i = 0; i < n; ++i){if(nums[i])sum += 1;elsesum -= 1;if(!m.count(sum))m[sum] = i;elsemaxlen = max(maxlen, i-m[sum]);}return maxlen;} };

344 ms 78.5 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 525. 连续数组（前缀和+哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。