前綴和 & 哈希表求解連續(xù)數(shù)組

題目描述

這是 LeetCode 上的 525. 連續(xù)數(shù)組 ，難度為 中等。

Tag : 「前綴和」

給定一個二進(jìn)制數(shù)組 nums , 找到含有相同數(shù)量的 0 和 1 的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。

示例 1:

輸入: nums = [0,1]
輸出: 2
說明: [0, 1] 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
復(fù)制代碼

示例 2:

輸入: nums = [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。
復(fù)制代碼

提示：

• 1 <= nums.length <= 10^5105

• nums[i] 不是 0 就是 1

基本分析

根據(jù)題意，我們可以輕易發(fā)現(xiàn)如下性質(zhì)：

• 如果答案非 00，那么子數(shù)組長度必然為偶數(shù)，且長度至少為 22。

前綴和 + 哈希表

具體的，我們在預(yù)處理前綴和時(shí)，將 nums[i]nums[i] 為 00 的值當(dāng)做 -1?1 處理。

從而將問題轉(zhuǎn)化為：如何求得最長一段區(qū)間和為 00 的子數(shù)組。

同時(shí)使用「哈希表」來記錄「某個前綴和出現(xiàn)的最小下標(biāo)」是多少。

再結(jié)合「如果答案非 00，子數(shù)組長度至少為 22」的特性，我們讓循環(huán)從 22 開始，并在循環(huán)開始前往「哈希表」存入哨兵，從而實(shí)現(xiàn)不需要處理邊界問題。

PS. 哈希表常數(shù)還是比較大的，用數(shù)組模擬哈希表的卡常代碼見 P2。

代碼：

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        for (int i = 2; i <= n; i++) {
            if (!map.containsKey(sum[i - 2])) map.put(sum[i - 2], i - 2);
            if (map.containsKey(sum[i])) ans = Math.max(ans, i - map.get(sum[i]));
        }
        return ans;
    }
}
復(fù)制代碼

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        int ans = 0;
        int[] hash = new int[2 * n + 1];
        Arrays.fill(hash, -1);
        hash[0 + n] = 0;
        for (int i = 2; i <= n; i++) {
            if (hash[sum[i - 2] + n] == -1) hash[sum[i - 2] + n] = i - 2;
            if (hash[sum[i] + n] != -1) ans = Math.max(ans, i - hash[sum[i] + n]);
        }
        return ans;
    }
}
復(fù)制代碼

• 時(shí)間復(fù)雜度：O(n)O(n)

• 空間復(fù)雜度：O(n)O(n)

最后

這是我們「刷穿 LeetCode」系列文章的第 No.525 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們將先將所有不帶鎖的題目刷完。

在這個系列文章里面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應(yīng)的代碼模板。

為了方便各位同學(xué)能夠電腦上進(jìn)行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：github.com/SharingSour… 。

在倉庫地址里，你可以看到系列文章的題解鏈接、系列文章的相應(yīng)代碼、LeetCode 原題鏈接和其他優(yōu)選題解。

作者：宮水三葉的刷題日記
鏈接：https://juejin.cn/post/6969394878375526414
來源：掘金