n 정수 배열의 모든 쌍에 대한 f (a [i], a [j])의 합


난이도 쉽게
자주 묻는 질문 시스코 페이스북 서비스 인상 퍼블리 시스 사피엔 트
배열 해시 수학

문제 설명은 n 개의 정수 배열에있는 모든 쌍에 대해 f (a [i], a [j])의 합계를 알아 내도록 요청합니다. 1 <= i <j <= n 정수 배열.

n 정수 배열의 모든 쌍에 대한 f (a [i], a [j])의 합

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

설명

3,1 및 3,1 쌍만 쌍.

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

설명

여기에도 두 쌍의 (1, 3)이 있습니다.

암호알고리즘

  1. 선언 지도 설정하고 출력 0 및 체크섬 0합니다.
  2. 다음에서 시작하는 배열을 횡단합니다. i = 0나는 = n,
    1. 출력 + = (i * a [i]) – 체크섬 및 체크섬 + = a [i];
    2. 지도에서 a [i] -1이 키로 있는지 확인합니다.
      1. true 인 경우 맵의 a [i] -1 값을 출력에 추가하여 출력을 업데이트합니다.
      2. 지도에서 a [i] +1이 키로 존재하는지 확인합니다. 참이면지도의 a [i] +1 값을 출력에 추가하여 출력을 업데이트합니다.
    3. 어떤 조건도 만족하지 않으면 배열 요소의 빈도를 계산하여 맵에 저장하면됩니다.
  3. 출력을 반환합니다.

설명

우리는 정렬 정수, 우리의 임무는 위의 조건을 충족하는 배열에있는 모든 쌍의 합을 찾는 것입니다. 어떤 쌍도 주어진 조건을 만족하지 않으면 0을 반환합니다.이 문제를 해결하기 위해 우리는 지도 동시에 각 배열 요소에 대한 모든 작업을 수행하고 출력을 업데이트하고 맵을 확인합니다. 우리는 실제 출력을 주시하는 추가 변수를 사용할 것입니다.이를 체크섬이라고 부를 수 있습니다. 출력과 체크섬을 0으로 설정합니다. 이것이 n 정수 배열의 모든 쌍에 대해 f (a [i], a [j])의 합을 찾는 방법입니다.

예를 들어 보겠습니다.

Arr [] = {1, 2, 3, 1, 3}, 출력 : 0, 체크섬 : 0

  • 0 번째 인덱스 요소를 선택한 다음 수행 한 다음 해당 인덱스를 곱하고 체크섬을 빼고 출력에 추가합니다.

출력 : 0, 체크섬 : 1

지도 {1 = 1}, 모든 조건이 충족되지 않으므로 값을지도에 추가합니다.

  • 1 들어st 인덱스 요소에 대해 동일한 작업을 수행하지만 이번에는 첫 번째 if 문의 조건을 충족하고 업데이트 된 출력을 얻은 후 얻습니다.

업데이트 된 출력 : 0, 체크섬 : 3

지도 {1 = 1, 2 = 1}, 이번에도 발생과 함께 해당 값을지도에 추가합니다.

  • 2 들어nd 요소, 이전과 동일한 작업이 수행되었습니다. 이번에는 요소 a [i] -1을 찾고 업데이트 된 출력을 얻었습니다.

업데이트 된 출력 : 2, 체크섬 : 6

맵 {1 = 1, 2 = 1, 3 = 1}, 요소와 빈도를 더합니다.

  • 세 번째 요소의 경우 두 번째 if 문을 충족합니다. 즉, 맵에 a [i] +3 값이 포함 된 경우 다음과 같이 업데이트 된 출력을 얻은 후 다음을 따릅니다.

업데이트 된 출력 : 0, 체크섬 : 7, 맵 : {1 = 2, 2 = 1, 3 = 1}

  • 네 번째 요소의 경우 첫 번째 if 문을 전달한 후.

업데이트 된 출력 : 4, 체크섬 : 10

지도 {1 = 2, 2 = 1, 3 = 2}

그리고 Output : 4를 반환합니다.

암호

n 정수 배열의 모든 쌍에서 f (a [i], a [j])의 합을 찾는 C ++ 코드

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

n 정수 배열의 모든 쌍에서 f (a [i], a [j])의 합계를 찾는 Java 코드

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. HashMap을 사용하면 검색 / 삭제 / 삽입을 수행 할 수 있습니다. O (1). 따라서 n 정수 배열의 모든 쌍에 대한 f (a [i], a [j])의 합을 찾는 시간 복잡도는 선형으로 감소됩니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. HashMap에 n 개의 키를 삽입해야 할 수 있으므로 공간 복잡성은 선형입니다.