元の配列と同じ合計の個別の要素を持つサブ配列をカウントします


難易度 ミディアム
よく聞かれる Amazon (アマゾン) データブリック ファブ ハニーウェル 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から始めて、右がn未満、maxsaがk未満の場合に、サブ配列を検索するためにループに入ります。 次に、配列要素を配置し、その頻度を1ずつ増やします。現在の要素の頻度が1であるかどうかを確認します。または、それをさらに更新して、trueであることがわかった場合は、値を増やします。 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

複雑さの分析

時間の複雑さ

オン) where "N" 配列内の要素の数です。 配列をトラバースし、HashMapを使用したため、線形時間計算量を実現できました。

スペースの複雑さ

オン) where "N" 配列内の要素の数です。 入力を格納するために配列を使用し、N個の要素を格納するHashMapを使用したためです。 したがって、線形空間の複雑さが達成されます。