计算具有与原始数组相同的不同元素的子数组


难度级别 中等
经常问 亚马逊 Databricks 晶圆厂 霍尼韦尔 PayU 广场 Teradata数据 Yandex的
排列 哈希 哈希 滑动窗口

问题陈述

“计算具有与原始元素相同的不同元素的子数组 排列”表示您得到了一个整数数组。 问题陈述要求找出包含原始数组中包含的所有不同元素的子数组的总数。

使用案列

arr[] = {2, 1, 3, 2, 3}
5

说明:子数组⇒{2,1,3},{1,3,2},{1,3,2,3},{2,1,3,2}和{2,1,3,2 ,,3}包含所有不同的元素作为原始数组。

计算具有与原始数组相同的不同元素的子数组

arr[] = {2, 4, 3, 4, 1, 2}
4

说明:子数组⇒{3,4,1,2},{4,3,4,1,2},{2,4,3,4,1}和{2,4,3,4,1 ,,2}包含所有不同的元素作为原始数组。

计算具有与原始数组相同的不同元素的子数组的算法

1. Declare a map.
2. Add all the values of array into the map with 1 as each key’s value.
3. Find the size of the map, store it to k and clear the map.
4, Set output, right, and maxsa to 0.
5. Traverse the array, from i=0, to i < n(length of the array).
  1. While the right is less than n and maxsa is less than k,
    1. Insert arr[right] and increase its frequency by 1.
    2. Check if the map’s value of current array element (arr[right]) is equal to 1 if true then increase the count of maxsa by 1.
  2. Increase the count of right by 1.
  3. If maxsa is equal to k, then update output à output += (n - right + 1).
  4. Insert the value of current arr[left] and decrease its frequency by 1.
  5. If the map’s arr[left] is equal to 0, then decrease the value of maxsa by 1.
6. Return output.

说明

我们给了 整数 数组,要求我们找出包含原始数组中所有不同元素的子数组的总数。 为此,我们将使用 哈希。 这是解决此代码的有效方法。

声明一个 地图。 我们将遍历整个数组,并将每个元素仅以1的频率放入映射中,因为我们不想计算每个元素的频率。 这只是想知道给定数组中存在多少个唯一键。 我们将地图的大小存储到变量k中并清除地图。

我们将遍历整个数组。 但是在此之前,我们将output的值right和maxsa设置为0。从0开始,我们将再次循环搜索子数组,而right小于n且maxsa小于k。 现在,我们将放置数组元素并将其频率增加1。我们将检查当前元素的频率是否为1。或者我们只是将其更新为更多的频率,如果发现它是正确的,则增加该值maxsa。

出来后 while循环,您将拥有一个递增的maxsa值,如果它等于k,则将输出更新为n-right +1。 正如我们已经将数组元素的值放入映射中一样。 现在我们将其频率降低1,并检查arr [left]值是否等于0并降低maxsa值。 每当我们发现maxsa的值等于k时,我们都会更新输出值。

代码

C ++代码对子数组的总数与原始数组相同的子数组进行计数

#include<iostream>
#include<unordered_map>

using namespace std;

int getSubArrayDistinct(int arr[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[arr[i]] = 1;

    int k = MAP.size();

    MAP.clear();

    int output = 0, right = 0, maxsa = 0;
    for (int left = 0; left < n; ++left)
    {
        while (right < n && maxsa < k)
        {
            ++MAP[ arr[right] ];

            if (MAP[ arr[right] ] == 1)
                ++maxsa;

            ++right;
        }
        if (maxsa == k)
        {
            output += (n - right + 1);
        }
        --MAP[ arr[left] ];

        if (MAP[ arr[left] ] == 0)
        {
            --maxsa;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 1, 3, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getSubArrayDistinct(arr, n);
}
5

Java代码来计算具有与原始数组相同的不同元素的子数组

import java.util.HashMap;

class SubarrayWithDistinctEle
{
    public static int getSubArrayDistinct(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>()
        {
            @Override
            public Integer get(Object key)
            {
                if(!containsKey(key))
                    return 0;
                return super.get(key);
            }
        };

        for (int i = 0; i < n; ++i)
            MAP.put(arr[i], 1);
        int k = MAP.size();

        MAP.clear();

        int output = 0, right = 0, maxsa = 0;
        for (int left = 0; left < n; ++left)
        {
            while (right < n && maxsa < k)
            {
                MAP.put(arr[right], MAP.get(arr[right]) + 1);

                if (MAP.get(arr[right])== 1)
                {
                    ++maxsa;
                }

                ++right;
            }
            if (maxsa == k)
            {
                output += (n - right + 1);
            }

            MAP.put(arr[left], MAP.get(arr[left]) - 1);

            if (MAP.get(arr[left]) == 0)
                --maxsa;
        }
        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2, 1, 3, 2, 3};
        int n=arr.length;
        System.out.println(getSubArrayDistinct(arr, n));
    }
}
5

复杂度分析

时间复杂度

上) 哪里 “N” 是数组中元素的数量。 由于我们遍历了数组并使用了HashMap,这使我们实现了线性时间复杂度。

空间复杂度

上) 哪里 “N” 是数组中元素的数量。 因为我们使用了一个数组来存储输入,并且使用了一个HashMap来存储N个元素。 因此,实现了线性空间复杂度。