This is the third day of my participation in Gwen Challenge

Topic describes

This is a 525. Contiguous array on LeetCode with medium difficulty.

Tag: prefix and

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.Copy the code

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.Copy the code

Tip:

  • 1 <= nums.length <=
    1 0 5 10^5
  • Nums [I] is either 0 or 1

Fundamental analysis

We can easily find the following properties:

  • If the answer is not 000, then the subarray must be even in length and at least 222 in length.

Prefix and + hash table

Specifically, nums[I]nums[I]nums[I] 000 is treated as −1-1−1 when preprocessing prefix sums.

The problem then becomes: how to find the longest interval and the subarray of 000.

Also use a hash table to record what the minimum subscript for a certain prefix and occurrence is.

Combined with the “if the answer is not 000, the subarray is at least 222 in length” feature, we let the loop start at 222 and go to the “hash table” at the beginning of the loop to store sentinels, thus eliminating the need to deal with bounds.

PS. Hash table constant is relatively large, with array simulation hash table card code see P2.

Code:

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]));
        }
        returnans; }}Copy the code
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]);
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.525 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.