@@ -0,0 +1,2649 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.Arrays;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * 525. Contiguous Array%0A * %3Cp%3E%0A * Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.%0A * %3Cp%3E%0A * Example 1:%0A * Input: %5B0,1%5D%0A * Output: 2%0A * Explanation: %5B0, 1%5D is the longest contiguous subarray with equal number of 0 and 1.%0A * Example 2:%0A * Input: %5B0,1,0%5D%0A * Output: 2%0A * Explanation: %5B0, 1%5D (or %5B1, 0%5D) is a longest contiguous subarray with equal number of 0 and 1.%0A * Note: The length of the given binary array will not exceed 50,000.%0A * %3Cp%3E%0A * Related Topics: Hash Table%0A * Similar Questions: (M) Maximum Size Subarray Sum Equals k%0A */%0Apublic class ContiguousArray %7B%0A%0A    /**%0A     * Hash Table.%0A     * Use an integer, count, to track the difference between # of 0s and # of 1s.%0A     * Whenever the difference is the same, there are equal # of 0s and 1s in between.%0A     * The count ranges from -n (all 1s) to n (all 0s).%0A     * So we can create a 2*n + 1 long array, as a map, to store the first index of this count.%0A     * When there is another count, we can subtract and check the length.%0A     * Note that when there is no element in the array, count = 0 still holds.%0A     * This is a special case that when 0s and 1s are equal from the beginning to current index.%0A     */%0A    public int findMaxLength(int%5B%5D nums) %7B%0A        int n = nums.length;%0A        int%5B%5D countToIndex = new int%5B2 * n + 1%5D;%0A        Arrays.fill(countToIndex, -2); // Fills with -2 since countToIndex%5Bn%5D is -1.%0A        countToIndex%5Bn%5D = -1; // When # of 0s and # of 1s are the same from beginning to i, the length should be i + 1.%0A        int maxLength = 0;%0A        int count = 0;%0A        for (int i = 0; i %3C n; i++) %7B%0A            count += (nums%5Bi%5D == 0 ? 1 : -1);%0A            if (countToIndex%5Bcount + n%5D %3E -2) %7B%0A                maxLength = Math.max(maxLength, i - countToIndex%5Bcount + n%5D);%0A            %7D else %7B  // No such count appeared yet.%0A                countToIndex%5Bcount + n%5D = i;%0A            %7D%0A        %7D%0A        return maxLength;%0A    %7D%0A%0A    /**%0A     * Hash Table.%0A     * Use map directly.%0A     */%0A    public int findMaxLength2(int%5B%5D nums) %7B%0A        Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A        map.put(0, -1);%0A        int count = 0;%0A        int maxLength = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            count += (nums%5Bi%5D == 0 ? 1 : -1);%0A            if (map.containsKey(count)) %7B%0A                maxLength = Math.max(maxLength, i - map.get(count));%0A            %7D else %7B%0A                map.put(count, i);%0A            %7D%0A        %7D%0A        return maxLength;%0A    %7D%0A%7D%0A

add 525. Contiguous Array