计数为1的最长子数组比计数为0的最长子数组


难度级别 易得奖学金
经常问 Accenture 亚马逊 Samsung
排列 哈希

我们给了 排列 整数数组仅包含1和0。 问题陈述要求找出最长的子数组的长度,该子数组的数量为1的位数仅比子数组中的0的位数大XNUMX。

使用案列

输入:

arr [] = {1,0,1,1,0,0,0}

输出:

5

说明:

从0到4的索引{1、0、1、1、0},共有三个 1和两个0。 1的计数多于0的计数。

输入:

arr [] = {1,0,1,0,0}

输出:

3

说明:

从0到2的索引{1,0,1},有两个1和一个0。 1的计数多于0的计数。

算法

  1. 声明地图。
  2. 将sum和outputLength设置为0。
  3. 遍历数组,而i = 0到i <n。
    1. 如果为true,则检查arr [i]是否等于0,然后将-1加到总和上。
    2. 否则将+1相加。
    3. 检查是否 总和相等 为1,然后将outputLength的值增加1。
    4. 否则,检查地图是否不包含总和(如果为true),然后将i的总和和当前值与总和一起放入地图。
    5. 检查地图是否包含(sum-1)。
    6. 如果outputLength小于i-index(地图中的总和值)。
      1. 如果为true,则将outputLength更新为i-index。
  4. 返回输出长度。

说明

我们将声明一个 地图。 在该图中,如果条件满足,我们将存储sum的值和索引的当前值。 取两个变量并将sum设置为0并将outputLength设置为0。在遍历数组时,我们将选择数组的每个元素,并检查arr [i]是否等于0,如果发现等于,则将添加-1求和并将其存储到求和,否则,如果我们未找到0,则将正数加1求和并将其存储到求和。

负1和正1背后的原因是,我们将所有0都假装为-1并将它们加1,所以我们总是得到0。 但是,我们将检查总和是否为正1,这表示我们将再得到一个1,然后再加上0。

假设,如果将1假装为-0,则将取1、0、1,我们将使用前0个数字获得2,使用第三个数字获得条件成立。 我们得到了一个1和0的子数组,其中的一个数比1多了0。我们得到了满足的条件。 这就是为什么我们将在算法的下一步中寻找和是否等于1并更新outputLength的长度的原因。 在最后一个语句中,如果获得新的输出长度,则需要使用当前的outputLength更新前一个,然后返回outputLength。

实施

最长子数组的C ++程序的计数为1s比计数为0多一

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

最长子数组的Java程序,其计数为1s比计数为0多一

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

计数为1s大于0s的最长子数组的复杂度分析

时间复杂度

O(N) 哪里 “ n”  是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n”  是数组中元素的数量。