題目連結:
題目意譯:
給定一個二元陣列 nums,回傳擁有等量的 0 和 1 的最長連續(xù)子陣列之長度。
限制:
1 ≦ nums.length ≦ 10 ^ 5
nums[i] 只會是 0 或是 1。
範例測資:
範例 1:
輸入: nums = [0,1]
輸出: 2
解釋: [0, 1] 為擁有等量的 0 和 1 之最長連續(xù)子陣列。
範例 2:
輸入: nums = [0,1,0]
輸出: 2
解釋:[0, 1](或是 [1, 0])為擁有等量的 0 和 1 之最長連續(xù)子陣列。
解題思維:
核心精神有點類似
這題——先將 0 當作「-1」、 1 當作「1」來把 nums 中前 X 個數(shù)字加總(假設總和值為 c)。如果 c 這個總和值在先前有出現(xiàn)過,也就是存在一個 X',使得前 X' 個數(shù)字加總為 c(其中 X' < X),則代表第 X' + 1 ~ X 個數(shù)字即是一個擁有等量的 0 和 1 之連續(xù)子陣列。
而我們只要找一個盡可能小的 X'(也就是 c 最早的出現(xiàn)時間),便可以得到以第 X 個數(shù)字作為結尾的等量 0 、 1 之連續(xù)子陣列之最長長度(如果確實存在的話)。取出過程中出現(xiàn)的所有長度中的最大值即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。