525. Contiguous Array - Medium

前往題目

想法

• 沒什麼想法，看到subarray想到會不會是用sliding window，但貌似不是

思路

1. 遇到0就-1，遇到1就+1，記錄每個index的sum
2. 疊代的期間，遇到出現過的sum就更新最大subarray長度

簡單來說就是遇到同樣的sum的時候那兩個相同sum的index之間的0和1的數量一定是一樣的，可以參考以下影片所畫的圖

另外影片中分成0和其他總和來討論，但我覺得情況就只有一種，就是上述所說相同sum中間的01數量一定是一樣的

Code

class Solution {
    public int findMaxLength(int[] nums) {
        // Map <Sum, Index>
        HashMap<Integer, Integer> seen = new HashMap();
        
        // To handle the answer which starts from the beginning
        seen.put(0, -1);

        int ans = 0, count = 0;

        // Look through the numbers
        for (int i = 0; i < nums.length; ++i) {
            // -1 if encountered 0, otherwise +1
            count += (nums[i] == 0) ? -1 : 1;

            // Check if the sum has already appeared before
            if (seen.containsKey(count)) {
                // Update the maximum subarray length
                ans = Math.max(ans, i - seen.get(count));
            } else { // First time appears
                seen.put(count, i);
            }
        }
        return ans;
    }
}

2024/04/30

• 有趣的題目，看了一下之前的想法才想起來怎麼解