Leetcode -525- Contiguous array

[Blog link]

A path to learning at 🐔

[B].

Given a binary array nums, find one that contains the same number0 和 1And returns the length of the subarray. The sample1: Input: nums = [0.1] output:2Description: [0.1] is the same number0and1The longest continuous subarray of. The sample2: Input: nums = [0.1.0] output:2Description: [0.1] (or [1.0]) is of the same quantity0and1The longest continuous subarray of. Tip:1 <= nums.length <= 105Nums [I] is not0is1Hash table Related Topics 👍293 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Brute force method (this method makes no sense, traverses all subarrays)

Time complexity (O(n^2^))

Idea 2: Hash table

  • Since there are only two elements in the array, the sum of the subarray is (n/2) when the length of the subelements is n (n is positive even).
  • So we can replace 0 with -1 so that the sum of the subarrays is 0, and the problem becomes finding the maximum length of the continuous subarrays that sum to 0
  • And the last two problems we did had this idea, by fixing the prefix and the interval of continuity
  • Related topics link leetcode-523- continuous subarrays and
  • Daily question series
  • That is, the length of a continuous subarray can be determined by the difference between the sum of the prefixes
  • Prefix [I] = nums[0] +… + nums[i]
  • Nums [I] +… + nums[j] = prefix[j] – prefix[i-1]
  • If you just compute the sum of each subarray this way it’s no different than the brute force method or even order n more time
  • Prefix [j] -prefix [I]== 0
  • In other words, the maximum difference between j and I should be obtained when prefix[j] is equal to prefix[I]
  • Therefore, it can be considered to introduce hashmap for calculation, store the value of prefix[I] as the key in hashmap and record the current coordinate as value.
 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);
            // Find the prefix and array
            for (int i = 1; i < n; i++) {
                prefix[i] = prefix[i - 1] + (nums[i] == 0 ? -1 : 1);
                // If the current prefix sum is met, the calculation scope is entered
                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;
        }
Copy the code

Time complexity O(n)