连续数组


难度级别 中等
经常问 亚马逊 MakeMyTrip 摩根士丹利 Paytm
哈希 滑动窗口

给定一个 排列 仅由数字0和1组成。 我们必须找到由o和1相等组成的最长连续子数组的长度。

使用案列

输入

arr = [0,1,0,1,0,0,1]

输出

6

说明

最长的 连续子数组 标记为红色[0,1,0,1,0,0,1],其长度为6。

算法

  1. 将maxlen的值设置为0。
  2. 使用两个循环,在第一个循环中,将zer_count设置为0,将one_count设置为0。
  3. 如果值 特定索引处的数组 发现为0,然后将zero_count增加1。
  4. 否则,将one_count更新并增加1。
  5. 在每次迭代中,检查zero_count是否等于one_count,如果相等,则找出(maxlen和j-i + 1)之间更大的否。
  6. 返回maxlen

说明

我们的主要思想是找到最长的连续子数组的长度,该数组具有零和一个唯一值,因此我们的主要重点是找到该长度。

因此,我们将使用嵌套的for循环。 在外循环中,我们将zero_count和one_count的值初始化为0,因为在每次迭代从内循环出来后,我们都需要新的zero_count和one_count值来再次检查所有值。 我们将遍历循环,直到达到数组的长度为止。

现在,它将检查数组的每个单个值,如果arr [index]的值为0或1,如果它的值等于0,则将1_count的值更新并增加1,或者如果arr [index]的值增加如果发现为1,则将one_count的值更新并增加XNUMX。

现在,下一个if块将检查zero_count是否等于one_count,如果相等,则找出maxlen和j-i + 1之间的较大数字并将较大的数字存储在maxlen中。

使用案列

假设给定数组:arr [] = {1,0,0,1,0,1,0}

zero_count = 0,one_count = 0,maxlen = 0

在i = 0时=> j = i

j = 0

在arr [j]不等于0时,则one_count ++,表示one_count = 1

j = 1

在arr [j]等于0时,则zero_count ++,表示zero_count = 1

在此位置,如果执行了块,它将在maxlen和j-i + 1之间给出更大的否,并在maxlen中返回2

j = 2

在arr [j]等于0时,则zero_count ++,表示zero_count = 2

j = 3

在arr [j]不等于0的情况下,one_count ++表示one_count = 2

在此位置,如果执行块,则它在maxlen和j-i + 1之间给出更大的否,并在maxlen中返回4。

j = 4

在arr [j]等于0时,则zero_count ++,表示zero_count = 3

j = 5

在arr [j]不等于0的情况下,one_count ++表示one_count = 3

在此位置,如果执行块,则它在maxlen和j-i + 1之间给出更大的否,并在maxlen中返回6。

j = 6

在arr [j]等于0时,则zero_count ++,表示zero_count = 4

并且它会不断循环,直到所有条件都失败为止。

并返回maxlen为6。

实施

连续数组的C ++程序

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

连续数组的Java程序

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

连续数组的复杂度分析

时间复杂度

O(N * N) 哪里 N 是给定数组的大小。

空间复杂度

O(1) 因为我们在这里不使用任何多余的空间。

参考