計算給定總和  


難度級別 容易獎學金
經常問 ol石 亞馬遜 事實集 遠足
排列 哈希 數學 排序

在問題“具有給定總和的計數對”中,我們給出了一個整數 排列[]和另一個數字表示“ sum”,則必須確定給定數組中兩個元素中的任何一個是否具有等於“ sum”的總和。

例  

輸入:

arr [] = {1,3,4,6,7}和sum = 9。

輸出:

“給定的元素 總和”,因為“ 3”和“ 6”的總和等於 到“ 9”。

輸入:

arr [] = {11,3,5,7,10}和sum = 20。

輸出:

“沒有找到具有給定總和的元素”,因為沒有任何數字的總和等於“ 8”。

算法  

  1. 聲明一個 Wi-Fi:.
  2. 從0到'i'小於數組的長度。
    1. 將j設置為sum-arr [i]。
    2. 檢查集合中是否包含“ j”,如果為true,則打印j和arr [i],這將是一對。
    3. 否則將arr [i]添加到集合中。

解釋  

我們給出了一個問題說明,其中給出了整數數組和一個數字“ sum”。 我們的任務是確定數組是否具有兩個總和等於給定“和”的元素。

我們的主要思想是使用HashSet並找到一對。 為此,我們將在遍歷時存儲sum和數組的每個值的差,因為一對具有這兩個元素,給定的sum是查找另一個元素的關鍵,這就是為什麼我們將所有array元素存儲到集合中的原因並查看其中是否存在成對的元素之一。

也可以看看
擺動排序

為了找出答案,我們將使用哈希方法。

讓我們舉個例子:

arr [] = {1,4,45,6,10,8};

  • i = 0,myset,sum = 16;

j = sum-arr [i];

即j = 16-1 = 15,並且肯定不會在地圖中顯示“ j”。

因此,它會將myrr中的arr [i]添加為“ 1”。

  • i = 1,myset = {1},sum = 16;

j = sum-arr [i];

即j = 16-4 = 12,並且在地圖中肯定沒有'j'。

因此,它會將myrr中的arr [i]添加為“ 4”。

  • i = 2,myset = {1,4},sum = 16;

j = sum-arr [i];

即j = 16-45 = -29,並且肯定不會在地圖中出現“ j”。

因此,它會將myrr中的arr [i]添加為“ 45”。

  • i = 3,myset = {1,4,45},sum = 16;

j = sum-arr [i];

即j = 16-6 = 10且j不存在於地圖中。

因此,它會將myrr中的arr [i]添加為“ 6”。

  • i = 4,myset = {1,4,45,6},sum = 16;

j = sum-arr [i];

即j = 16-10 = 6並且j存在於地圖中。

這是我們找到對的另一個元素的地方。 我們已經在16和10上完成了操作。

然後我們打印:

“給定總和為16的找到的元素是(10,6);

這意味著數組中存在兩個元素,其總和等於“ sum”。

履行  

給定總和的計數對的C ++程序

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}
Found elements with the given sum as 16 is (10, 6)

給定總數的Count對Java程序

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

給定總和的計數對的複雜度分析  

時間複雜度

O(N) 因為整個數組只需要遍歷一次。

也可以看看
向People Leetcode解決方案分發糖果

空間複雜度

O(N) 因為哈希映射已用於存儲數組元素。

參考文獻