LeetCode_ Prefix and_ Hash table_ Medium_ 525. Continuous array

1. subject

Given a binary array nums , Find the same number of 0 and 1 The longest continuous subarray of , And returns the length of the subarray .

Example 1：
Input : nums = [0,1]
Output : 2
explain : [0, 1] It's the same number 0 and 1 The longest continuous subarray of .

Example 2：
Input : nums = [0,1,0]
Output : 2
explain : [0, 1] ( or [1, 0]) It's the same number 0 and 1 The longest continuous subarray of .

Tips ：
1 <= nums.length <= 10⁵
nums[i] No 0 Namely 1

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/contiguous-array

2. Ideas

（1） The prefix and
The general idea is to use prefixes and arrays , namely preSum[i] preservation nums[0…i - 1] And , Then use two more layers for Loop through the sub array that meets the condition of the topic , If you qualify , Update res, Otherwise, continue to traverse . After traversal, return directly to res that will do . But in LeetCode When submitting on “ Time limit exceeded ” A hint of ！ This shows the method （ The time complexity is O(n²)） Still need to be optimized , See ideas for specific optimization methods 2.

（2） The prefix and & Hashtable
Train of thought reference The LeetCode User questions .

① Right way of thinking 1 Initialize array in code preSum Make a change to the operation of , Use preSum[i] To record nums[0…i - 1] The elements in 0 And elements 1 The difference in the number of ：

preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);

obviously , We can know :
When preSum[i] > 0 when ,preSum[i] Express nums[0…i - 1] in 1 Than 0 More numbers ;
When preSum[i] < 0 when ,|preSum[i]| Express nums[0…i - 1] in 1 Than 0 A small number ;
When preSum[i] = 0 when ,nums[0…i - 1] in 0 and 1 The number of is equal ;

② Define hash table hashMap, To hold preSum[i] And its corresponding subscript i;

③ Because the length of the sub array that meets the conditions of the topic is at least 2, So it's traversing preSum Time subscript 2 Start . In the process of traversing , use hashMap Save in a sub array 0、1 The minimum subscript of the number of element differences , In the following code ：

if (!hashMap.containsKey(preSum[i - 2])) {
    
    hashMap.put(preSum[i - 2], i - 2);
}

④ Also judge preSum[i] Does it exist in hashMap in , If there is , Then set the subscript position appearing before as preIdx = hashMap.get(preSum[i]),
So the corresponding nums[0…preIdx - 1] Medium element 0 And elements 1 The number of differences is k, for example [0, 1, 1, 1],k = 2,preIdx = 4
At the same time, we can also know nums[0…i - 1] Medium element 0 And elements 1 The number of differences is also k, for example [0, 1, 1, 1, 0, 1],k = 2,i = 6
So at this time nums[preIdx…i - 1] Medium element 0 And elements 1 The number of must be equal , That is, the sub array that meets the conditions is [0, 1], The corresponding length is i - preIdx, Update at this time res that will do .

The derivation process is also relatively simple ：

 from  preSum[i] = k -> nums[0...i - 1]  Medium element  0  And elements  1  The number of differences is  k,
 from  preSum[preIdx] = k -> nums[0...preIdx - 1]  Medium element  0  And elements  1  The number of differences is  k, And  preIdx < i
 because  nums[0...preIdx - 1]  contain  nums[0...i - 1], So clearly  nums[0...preIdx - 1]  Medium element  0  And elements  1  The number difference is  k  The interval of is just right 
 yes  nums[0...i - 1], So the remaining interval  nums[preIdx...i - 1]  Medium element  0  And elements  1  The number of must be equal .

3. Code implementation （Java）

// Ideas 1———— The prefix and 
class Solution {
    
    public int findMaxLength(int[] nums) {
    
        int res = 0;
        int length = nums.length;
        int[] preSum = new int[length + 1];
        for (int i = 1; i < length + 1; i++) {
    
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < length - 1; i++) {
    
            for (int j = i + 2; j < length + 1; j += 2) {
    
                int sum_ij = preSum[j] - preSum[i];
                if (sum_ij != 0 && (j - i) / sum_ij == 2 && (j - i) % sum_ij == 0) {
    
                    res = Math.max(res, j - i);
                }
            }
        }
        return res;
    }
}

// Ideas 2———— The prefix and  &  Hashtable 
class Solution {
    
    public static int findMaxLength(int[] nums) {
    
        int res = 0;
        int length = nums.length;
        int[] preSum = new int[length + 1];
        for (int i = 1; i < length + 1; i++) {
    
            preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 2; i <= length; i++) {
    
            if (!hashMap.containsKey(preSum[i - 2])) {
    
                hashMap.put(preSum[i - 2], i - 2);
            }
            if (hashMap.containsKey(preSum[i])) {
    
                int preIdx = hashMap.get(preSum[i]);
                res = Math.max(res, i - preIdx);
            }
        }
        return res;
    }
}