두 이진 배열에서 동일한 합계를 갖는 최장 스팬


난이도 중급
자주 묻는 질문 Accenture 시스코 과연 쿨리 자 SAP 연구소 Yandex 주차
배열 해시 해싱

문제 정책

각각 이진수를 포함하는 두 개의 배열이 제공됩니다. 문제 설명은 두 개의 이진 배열에서 동일한 합을 가진 가장 긴 범위를 찾을 것을 요청합니다. 즉, j가 i 및 arr1 [보다 크거나 같은 방식으로 (i, j)에서 최대 길이의 공통 하위 배열을 찾는 것입니다. i] + arr1 [i + 1] + arr1 [i + 2] +…. + arr1 [j] = arr2 [i] + arr2 [i + 1] + arr2 [i + 2] +…. + arr2 [j].

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

arr2[] = {1,0,1,0,1,1,0,1}
4

설명 : 인덱스 4에서 0까지 두 하위 배열의 합계가 같기 때문에 가장 높은 공통 범위의 길이는 3입니다.

두 이진 배열에서 동일한 합계를 갖는 최장 스팬

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

arr2[] = {0, 1, 1, 0, 0, 0}
4

설명 : 인덱스 4에서 0까지 두 하위 배열의 합계가 동일하므로 가장 높은 공통 범위의 길이는 3입니다.

 

암호알고리즘

1. Declare an array of size n.
2. Find the difference of each element’s index of both of the arrays such that arr[i]=arr1[i]-arr2[i].
3. Declare the HashMap.
4. Set sum to 0 and maxLength to 0.
5. From i=0 to i<n.
    1. Add up the value of arr[i] and sum into the sum.
    2. Check if sum ==0, then update the maxLength=i+1.
    3. Check if the map contains the sum, then update the maxLength to the maximum between maxLength and i-key’s value.
    4. Else put the sum and its index into the map.
6. Return maxLength.

설명

우리는 각각 0과 1의 이진수를 포함하는 두 개의 이진 배열을 제공했습니다. 우리는 [i, j]의 가장 긴 공통 범위를 찾아야합니다. , 동일하고 공통 스팬의 가장 긴 길이입니다. 이를 위해 생성 된 배열의 i 번째 위치에있는 각 i 번째 인덱스 요소의 차이를 저장할 Hashing과 추가 배열을 살펴 보겠습니다.

새로 생성 된 배열의 값을 키로 맵에 저장하고 인덱스를 값으로 저장한다는 점에서 맵을 생성합니다. 해당 인덱스의 최대 값을 알아 내고이를 가장 긴 길이로 최대 값을 찾아 저장하기 위해 만든 maxLength와 비교할 것입니다. 그러나 그 전에, 우리는 arr [i]를 선택하고 arr [i]와 함께 더한 다음 sum에 저장합니다. 합계가 0인지 확인하고 maxLength를 i + 1로 업데이트합니다. 이것은 마지막 인덱스 요소의 값을 처리하기위한 것입니다.

맵에 합계가 포함되어 있는지 확인한 다음 maxLength와 인덱스 사이의 최대 값을 찾아 최대 길이를 업데이트합니다. 지도[합집합]. 그렇지 않으면 합계와 색인을지도에 넣습니다. 두 배열의 차이로 만들고 초기화 한 배열이 중요한 역할을합니다. 그 후 maxLength에 값이 있고 maxLength를 반환합니다.

 

두 이진 배열에서 동일한 합계를 가진 가장 긴 스팬을 찾는 코드

C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

int longestCommonSum(int arr1[], int arr2[], int n)
{
    int arr[n];
    for (int i=0; i<n; i++)
        arr[i] = arr1[i] - arr2[i];

    unordered_map<int, int> hM;

    int sum = 0;

    int max_len = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];

        if (sum == 0)
            max_len = i + 1;

        if (hM.find(sum) != hM.end())
            max_len = max(max_len, i - hM[sum]);

        else
            hM[sum] = i;
    }
    return max_len;
}

int main()
{
    int arr1[] = {0, 1, 0, 1, 1, 1, 1};
    int arr2[] = {1, 1, 1, 1, 1, 0, 1};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout << longestCommonSum(arr1, arr2, n);
    return 0;
}
6

 

자바 코드

import java.util.HashMap;

class LargestSubArr01
{
    public static int longestCommonSum(int[] arr1, int[] arr2, int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = arr1[i] - arr2[i];

        HashMap<Integer, Integer> hM = new HashMap<>();

        int sum = 0;
        int max_len = 0;

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

            if (sum == 0)
                max_len = i + 1;

            if (hM.containsKey(sum))
                max_len = Math.max(max_len, i - hM.get(sum));

            else
                hM.put(sum, i);
        }
        return max_len;
    }
    public static void main(String args[])
    {
        int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
        int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
        int n = arr1.length;
        System.out.println(longestCommonSum(arr1, arr2, n));
    }
}
6

 

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 여기서는 배열을 한 번 순회했으며 순서가 지정되지 않은 맵을 사용했기 때문입니다. 삽입, 삭제 및 검색 작업은 O (1) 시간 복잡도를 갖습니다. 따라서 두 이진 배열에서 동일한 합계를 가진 가장 긴 범위에 대한 전체 알고리즘은 선형 시간 복잡도를 갖습니다.

공간 복잡성

무순 맵 또는 해시 맵을 사용했기 때문에 선형 공간 복잡성도 있습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.