n個整數數組中所有對上的f(a [i],a [j])的總和  


難度級別 容易獎學金
經常問 思科 Facebook 遠足 陽獅精明
排列 哈希 數學

問題陳述要求找出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 = 0i = n,
    1. 輸出+ =(i * a [i])–校驗和和校驗和+ = a [i];
    2. 檢查映射中是否存在a [i] -1作為鍵。
      1. 如果為true,則通過將映射的a [i] -1的值添加到輸出中來更新輸出。
      2. 檢查a [i] +1是否作為鍵出現在地圖中。 如果為true,則通過將映射的a [i] +1的值添加到輸出中來更新輸出。
    3. 如果沒有一個條件滿足,則只需計數數組元素的頻率並將其存儲到映射中即可。
  3. 返回輸出。

解釋

我們有一個 排列 整數,我們的任務是找出滿足上述條件的數組中存在的所有對的總和。 如果沒有一個對滿足給定條件,那麼我們簡單地返回0。為解決這個問題,我們將使用 地圖 同時對每個數組元素進行所有操作,並更新輸出並檢查Map。 我們將使用一個額外的變量來關注我們的實際輸出,我們可以將其稱為校驗和。 我們將輸出和校驗和設置為0。這就是我們在n個整數數組中的所有對上求f(a [i],a [j])之和的方式。

也可以看看
最小元素正好重複K次

讓我們考慮一個例子:

Arr [] = {1,2,3,1,3},輸出:0,校驗和:0

  • 我們將選擇第0個索引元素,然後執行,然後乘以其索引,然後減去校驗和,然後將其添加到輸出中,我們得到

輸出:0,校驗和:1

映射{1 = 1},任何條件都不滿足,因此我們將值添加到映射中。

  • 對於1st 索引元素,執行相同的操作,但是這次,它將滿足第一個if語句的條件,並且在獲取更新的輸出之後,我們得到了。

更新的輸出:0,校驗和:3

映射{1 = 1,2 = 1},這次我們也將該值及其出現的值添加到映射中。

  • 對於2nd 元素,執行與之前相同的操作,這次它找到元素a [i] -1,我們得到了更新的輸出:

更新的輸出:2,校驗和:6

映射{1 = 1,2 = 1,3 = 1},將元素及其頻率相加。

  • 對於第3個元素,它滿足第二個if語句,這意味著如果映射包含值a [i] +1,則遵循它,然後在得到更新後的輸出之後:

更新的輸出:0,校驗和:7,映射:{1 = 2,2 = 1,3 = 1}

  • 對於第四個元素,在傳遞第一個if語句之後。

更新的輸出:4,校驗和:10

映射{1 = 2,2 = 1,3 = 2}

我們將返回輸出:4

推薦碼  

C ++代碼在n個整數數組中的所有對上查找f(a [i],a [j])的和

#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

Java代碼在n個整數數組中的所有對上查找f(a [i],a [j])的和

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) 哪裡 “ n” 是數組中元素的數量。 HashMap的用法允許我們在以下位置執行搜索/刪除/插入 O(1)。 因此,用於在n個整數陣列中的所有對上查找f(a [i],a [j])之和的時間複雜度降低為線性。

也可以看看
字型

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 由於我們可能必須在HashMap中插入n個鍵,因此空間複雜度是線性的。