寻找具有相等数量的0和1的最大子数组

Question

我有一个只包含0和1的数组。我需要找到包含相等数量的0和1的最大子数组。一种朴素的方法是使用复杂度为O(n^2)的算法，在外层循环中遍历每个元素，在内层循环中计算可能的子数组并更新最大大小，如果找到的话。是否有其他更好的方法（类似于O(n)）可以使用？谢谢！

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

- John Lui

Answer 1

这是一个O(n)时间复杂度和O(n)空间复杂度的算法。我不确定它是否最优，但它可以避免二次时间复杂度。

基本思路如下：假设你从数组的左边开始扫描到右边，在每一步记录1的数量与0的数量之间的差异。如果你在每个步骤中写出这些值，你会得到像这样的东西：

  1,   0,   1,    0,    0,   0,   0
0,   1,   0,   1,    0,    -1,  -2,  -3

如果你有一个由相同数量的0和1组成的子数组，那么子数组开始时0和1的净差将等于子数组后面的净数。因此，可以将此问题重新构造为试图找到两个在辅助数组中相等且尽可能远离的值。

好消息是数组中的每个条目都介于-n和+n之间，因此可以制作一个2n+1元素表格，并在其中存储每个数字第一次和最后一次出现的索引。从那里开始，很容易找到最长的范围。总体而言，这需要O(n)空间，并且所有内容都可以在O(n)时间内填充和搜索。

希望这能帮到你！

- templatetypedef

---

好的，这样就可以了。嗯。很棒的想法。 :) - John Lui

以下序列的顺序如何： 0 0 0 0 1 0 1 0 0 0 - Piyush Srivastava

这将给出数组0，-1，-2，-3，-4，-3，-4，-3，-4，-5，-6。由-3限定的范围或由-4限定的范围都可以得到您要查找的内容。不过也许我漏掉了什么？ - templatetypedef

@templatetypedef，感谢您的分享！我已经基于您的想法添加了一个实现，链接在这里 - https://dev59.com/010Z5IYBdhLWcg3wrByH#53900838 - seeker

Answer 2

首先将您的零转换为-1。然后，您需要寻找零和的最大子数组。这个算法可以在这里找到。

- vib

---

但是，接下来的问题是找到所有和为0的子数组，并找出最大长度。找到一个子数组本身的时间复杂度为O(n)，然后我将重复这个过程（在最坏情况下，可能需要n次），使其再次变为O(n^2)。 - John Lui

如果你查看我给你的链接，你会发现那里有一个O(n)的答案。但是另一个答案更具体针对这个问题，而且更好... - vib

该链接中的算法找到的是第一个子数组，而不是最长的子数组。此外，它不会默认数据的二进制性质。 - Jared Goguen

Answer 3

public int equalNumber(int arr[]){

    int sum[] = new int[arr.length];
    sum[0] = arr[0] == 0? -1 : 1;
    for(int i=1; i < sum.length; i++){
        sum[i] = sum[i-1] + (arr[i] == 0? -1 : 1);
    }

    Map<Integer,Integer> pos = new HashMap<Integer,Integer>();
    int maxLen = 0;
    int i = 0;
    for(int s : sum){
        if(s == 0){
            maxLen = Math.max(maxLen, i+1);
        }
        if(pos.containsKey(s)){
            maxLen = Math.max(maxLen, i-pos.get(s));
        }else{
            pos.put(s, i);
        }
        i++;
    }
    return maxLen;
}

- SWAR0714

---

如果编辑一下并讨论如何回答问题以及运行复杂度，它可能会得到改进。 - paisanco

如果有人有更好的方法，请告诉我，我现在分享的是我的方法。 - SWAR0714

两个元素之间的和为零，当且仅当其前缀和相等。因此，如果您在计算每个前缀和时使用哈希表，则可以找到具有相同前缀和的两个索引，并且它们之间的子数组之和为零。 - EmptyData

Answer 4

解决方案是什么？

因此，在这个解决方案中，它将考虑所有的子数组，并且对于每个子数组，它将计算出其中存在的0和1的总数。如果子数组包含相同数量的0和1，则根据需要更新最大的数组。 该解决方案的时间复杂度为O(n^3)，因为在n个元素的数组大小中有n^2个子数组，而找到0和1的计数需要O(n)。我们可以通过在常量时间内计算0和1的计数来优化方法，使其运行O(n^2)。

我们如何解决这个问题？

在这里，我们可以使用映射来在线性时间内解决它。想法是用-1替换0，并找到具有0总和的最大子数组。

因此，为了找到最大子数组，请创建一个空映射，该映射将存储具有给定总和的第一个子数组的结尾。然后遍历给定的数组并在元素中维护总和。

• 如果第一次看到总和，则在映射中输入总和和索引。
• 如果之前看到过总和，则存在一个总和为0的子数组，该子数组以当前索引结束，并且如果当前子数组的长度更长，则更新最大子数组。

class Solution {
    // Function to find the largest subarray having an equal number
    // of 0's and 1's
    public static void findLargestSubarray(int[] nums)
    {
        // create an empty `HashMap` to store the ending index of the first
        // subarray having some sum
        Map<Integer, Integer> map = new HashMap<>();
 
        // insert (0, -1) pair into the set to handle the case when a
        // subarray with zero-sum starts from index 0
        map.put(0, -1);
 
        // `len` stores the maximum length of subarray with zero-sum
        int len = 0;
 
        // stores ending index of the largest subarray having zero-sum
        int end_index = -1;
 
        int sum = 0;
 
        // Traverse through the given array
        for (int i = 0; i < nums.length; i++)
        {
            // sum of elements so far (replace 0 with -1)
            sum += (nums[i] == 0)? -1: 1;
 
            // if the sum is seen before
            if (map.containsKey(sum))
            {
                // update length and ending index of largest subarray having zero-sum
                if (len < i - map.get(sum))
                {
                    len = i - map.get(sum);
                    end_index = i;
                }
            }
            // if the sum is seen for the first time, insert the sum with its
            // index into the map
            else {
                map.put(sum, i);
            }
        }
 
        // print the subarray if present
        if (end_index != -1)
        {
            System.out.println("[" + (end_index - len + 1) + ", " +
                                    end_index + "]");
        }
        else {
            System.out.println("No subarray exists");
        }
    }

时间复杂度：O(n)，需要额外O(n)的空间，其中n是输入的大小。

- Anushka Pandhere

Answer 5

受到@templatetypedef算法的启发，我用Python编写了代码，希望对某些人有所帮助。

def check_max_length(input_array):
    length = len(input_array)
    mapping_dict = {}
    max_length = 0
    for i in range(length):
        if input_array[i] not in mapping_dict.keys():
            mapping_dict[input_array[i]] = i
        else:
            max_length = max(max_length,i-mapping_dict[input_array[i]])
    return max_length

def find_max_substring_length(input_string):
    def_array = [0]
    zero_count = 0
    one_count = 0
    # difference between number of zeroes and ones
    def_zero_one = 0
    for i in range(len(input_string)):
        if input_string[i] == '1':
            one_count+=1
        else:
            zero_count+=1

        def_array.append(one_count-zero_count)
    max_substring = check_max_length(def_array)
return max_substring

input_string = '1000100'
substring_length = find_max_substring_length(input_string)
print(substring_length) // will give result as 2

- raviraja

Answer 6

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return 0;
        vector<int> arr(n,-1);
        arr[0]= (nums[0]==0)? -1:1 ;

        for(int i=1;i<n;i++)
        {
            arr[i] = arr[i-1] + ((nums[i]==0)? -1 : 1) ;
        }

        int sol=0;
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==0) sol = i+1;
            else
            {
                if(mp.find(arr[i])==mp.end())
                {
                    mp[arr[i]]=i;
                }
                else
                {
                    sol=max(sol,i-mp[arr[i]]);
                }
            }
        }
        return sol;
    }
};

- Pragati Verma

Answer 7

使用O(n)时间实现哈希映射。

int count=0, max_length=0;
        unordered_map<int,int> mp;
        mp[0] = -1;

        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i] == 0) count += -1;
            if(nums[i] == 1) count += 1;

            if(mp.find(count) != mp.end())
                max_length = max(max_length, i-mp[count]);
            else
                mp[count] = i;                        
        }

        return max_length;

希望这个代码块有所帮助。

- User001

Answer 8

这与@templatetypedef的答案密切相关。 然而，我并不是将其视为1和0的数量差异。我将其视为一种跟踪器，当看到1时递增，当看到0时递减。

这是一个经过测试的解决方案。

 /**
 * given an array of 0's and 1's return the length of the maximal
 * subarray that has only 0's and 1's
 * O(n) solution inspired by https://dev59.com/010Z5IYBdhLWcg3wrByH#31201586
 *
 * in           0    0    1    1
 * aux         0  -1   -2   -1   0
 * @param in
 * @return
 */
static int lenMaxSubArray(int[] in) {
    int maxLen = -1;
    int[] oneCount = new int[in.length + 1];
    oneCount[0] = 0;
    for (int i = 0; i < in.length; i++) {
        if (in[i] == 1) {
            oneCount[i + 1] = oneCount[i] + 1;
        } else {
            oneCount[i + 1] = oneCount[i] - 1;
        }
    }

    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < oneCount.length; i++) {
        List<Integer> list = map.getOrDefault(oneCount[i], new ArrayList<>());
        list.add(i);
        map.put(oneCount[i], list);
    }

    for (int i = 0; i < oneCount.length; i++) {
        List<Integer> list = map.get(oneCount[i]);
        if (list != null) {
            int start = list.get(0);
            int end = list.get(list.size() - 1);
            maxLen = Math.max(maxLen, end - start);
        }
    }

    return maxLen;
}

- seeker

Answer 9

使用 JavaScript 实现 @templatetypedef 算法，并修改为使用 map 来帮助查找最大长度

function findMaxLen(a) {
// secondary array, initialized with the first element as 0
let b = [0]
let sum = 0

// populate the secondary array and update the sum as per the algorithm
for (let i = 0; i < a.length; i++) {
    b[i + 1] = a[i] == 0 ? sum - 1 : sum + 1
    sum = b[i + 1]
}

// map of sum vs the first index of the secondary array with the sum value
let map = new Map()
let maxLen = 0

for (let i = 0; i < b.length; i++) {
    if (map.has(b[i]))
        maxLen = Math.max(maxLen, i - map.get(b[i]))
    else
        map.set(b[i], i)
}

return maxLen
}

- aakashdp

Answer 10

算法

我们使用HashMap映射来以(index,count)的形式存储条目。每当遇到一个计数时，我们在映射中创建一个条目，并稍后使用相应的索引来查找具有相等数量的零和一的最大子数组的长度，当再次遇到相同的计数时。

public class Solution {

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 1 ? 1 : -1);
            if (map.containsKey(count)) {
                maxlen = Math.max(maxlen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxlen;
    }
}





Time complexity : O(n). The entire array is traversed only once.

Space complexity : O(n). Maximum size of the HashMap map will be n, if all the elements are either 1 or 0.

- Ashwani Jha