preface

A daily question to do about prefix and the topic, here summarizes the next. 525. Contiguous arrays

The question:

Given a binary array nums, find the longest continuous subarray with the same number of 0s and 1s, and return the length of that subarray.

Example 1:

Input: nums = [0,1] Output: 2 Description: [0,1] is the longest continuous subarray with the same number of 0s and 1s.

Example 2:

Input: nums = [0,1,0] Output: 2 Description: [0,1] (or [1, 0]) is the longest continuous subarray with the same number of 0s and 1s.

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The prefix and

To solve this problem, you have to understand what prefix sum is. The prefix sum is essentially a line segment difference, such as an array of [….Ai….Aj…] Sum [j]-sum[I] is the sum of the values of the subscripts I +1 to j.

My train of thought

If the closed interval [I,j] contains the same number of zeros and ones, then the sum of the array values of the closed interval [I,j] must be half of (j-i+1), because half of the array values between [I,j] are 1. The code is as follows:

public int findMaxLength(int[] nums) {
        int[] sum = new int[nums.length+1];
        for (int i=1; i<=nums.length; i++){
            sum[i] = nums[i-1]+sum[i-1];
        }
        int maxLength = 0;
        for (int i=1; i<=nums.length; i++){
            for (int j=1; j<i; j++){
                int temp = sum[i] - sum[j]+nums[j-1];// Calculate the sum of the values of the interval [I,j] according to the prefix and
                int ans = i-j+1;
                if (temp*2 == ans){ // The sum is half of ans
                    maxLength = Math.max(maxLength, i-j+1); }}}return maxLength;
    }
Copy the code

The submission results are as follows:

The idea should be correct, but only 32 test cases have passed because of the timeout caused by the double for loop. @ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $@ $

The official answer key

The official solution is clever in two ways.

In the first place, since the elements of the array are all 0, 1, we can use 0 as -1.

Sum [I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; sum[I]=sum[j]; So sum[I] must be equal to sum[j]. So, to sum [I] in the hash table, and when there is a sum [j] this key in the hash table to exist, then the subscript range (I, j] elements and inevitable to 0.

The code is as follows:

public int findMaxLength2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int counter = 0, maxLength = 0;
        for (int i=0; i<nums.length; i++){
            if (nums[i] == 0)
                counter --;
            if (nums[i] == 1)
                counter ++;

            if (map.containsKey(counter)){
                maxLength = Math.max(maxLength, i-map.get(counter));
            }else{ map.put(counter, i); }}return maxLength;
    }
Copy the code