Leetcode-525 – Contiguous Arrays

<! –more–>

[Title description]

Given a binary array nums, find the longest contiguous subarray with the same number of zeros and ones, and return the length of that subarray. Example 1: Input: nums = [0,1] Output: 2 Description: [0,1] is the longest contiguous 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 contiguous subarray with the same number of 0s and 1s. Note: 1 <= nums.length <= 105 nums[I] is either 0 or 1 Related Topics hash table 👍 293 n0

[Title link]

LeetCode title link

[making address]

Code link

[Introduction]

Brute force (this method is meaningless, iterating through all subarrays)

Time complexity (n^2^)

Idea 2: a hash table

  • Since there are only 0 and 1 elements in the array, when the length of the subelements is n (n is positive even), the sum of the subelements is (n/2).
  • So we can replace 0 with negative 1 so that the sum of the subarray is 0, and the idea is to find the maximum length of the contiguous subarray and the sum of 0
  • The last two problems we’ve done have this idea in mind, with prefixes and continuums
  • Links to leetcode-523- contiguous subarrays and
  • One question of the day series
  • In other words, the length of the consecutive subarray can be determined by the difference between the prefixes and the values
  • Prefix [I] = nums[0] +… + nums[i]
  • Nums [I] +… + nums[j] = prefix[j] – prefix[i-1]
  • If you just compute the sum of each of these subarrays in this way, it’s no different than the brute force method or even O(n) more time
  • Prefix [j] -prefix [I]== 0 (prefix[j] -prefix [I]== 0
  • If prefix[j] and prefix[I] are equal, the difference between j and I is the largest
  • So you can consider using a HashMap to compute, storing the prefix[I] value as the key in the HashMap and record the current coordinate as value. Every time you compute the prefix sum, calculate Math.max(J-i).
public int findMaxLength(int[] nums) { int n = nums.length,max = 0; Map<Integer,Integer> map = new HashMap<>(); int[] prefix = new int[n]; prefix[0] = (nums[0] == 0 ? 1:1); map.put(prefix[0],0); For (int I = 1; i < n; i++) { prefix[i] = prefix[i - 1] + (nums[i] == 0 ? 1:1); If (prefix[I] == 0){Max = Math.max(I +1, Max); } if (map.containsKey(prefix[i])){ max = Math.max(i-map.get(prefix[i]),max); }else{ map.put(prefix[i], i); } } return max; }

Time complexity O(n)