Берілген сомамен жұптарды санау


Күрделілік дәрежесі оңай
Жиі кіреді Акколит Amazon Factset жорық
Array Hash математика Сұрыптау

Бүтін сан берілген массив n өлшемді және 'K' бүтін санының жиынтығы 'K' -ге тең болатын массивтегі жұптардың санын есептеу керек (бірегей болмау керек).

мысал

Кіру:

Arr = {1, 5, 7, 1}

K = 6

Шығару:

2

Берілген қосындымен санау жұптары үшін күштің шешімі

Негізгі ой

Біз берілген жиымның барлық жұптарын қайталай аламыз, содан кейін қосындысы К-ге тең жұптарды санауға болады.

Алгоритм

  1. Айнымалы жауап = 0 инициализациясы.
  2. 0-ден n-1 аралығында I үшін циклды іске қосыңыз
    1. I + 1-ден n-1 аралығында j үшін циклды іске қосыңыз;
      1. Егер arr [i] + arr [j] k-ге тең болса, онда 1-ге өсу керек.
  3. Жауапты қайтарыңыз.

Іске асыру

C ++ бағдарламасы

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]+a[j]==k){
                ans++;
            }
        }
    }
    cout<<"Number of pairs with the given sum are: "<<ans;
}
4 6
1  5  7 1
Number of pairs with the given sum are: 2

JAVA бағдарламасы

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]+a[j]==k){
                    ans++;
                }
            }
        }
    System.out.println("Number of pairs with the given sum are: "+ans);
  }
}

6 4
2 2 3 1 1 5
Number of pairs with the given sum are: 3

Берілген қосындымен санау жұптарының күрделілігін талдау

Уақыт күрделілігі

Біз барлық жұптарды қайталай отырып, шамамен N ^ 2 жұпты құрайтындықтан, уақыттың жалпы күрделілігі O (N ^ 2) құрайды.

Ғарыштың күрделілігі

Біз қосымша кеңістікті пайдаланған жоқпыз, сондықтан кеңістіктің қиындығы O (1).

Берілген сомамен санау жұптарына арналған хэштеу тұжырымдамасы

Негізгі ой

Біз берілген массивтегі әр санның жиілігін сақтайтын хэш кестесін жүргіземіз.

Енді біз массивтің үстінен қайталаймыз және мәні k-arr [i] -ге тең болатын барлық элементтерді қосамыз.

Бірақ біз бір шартты тексеруіміз керек:

Егер arr [i] k-arr [i] -ге тең болса, онда біз өз жауабымыздан 1-ді алып тастаймыз, өйткені біз нақты жұптарды табуымыз керек, сондықтан жұп үшін arr [i] -ді екі рет ала алмаймыз, сондықтан біз мұны алып тастаймыз біздің жауабымыздан.

Алгоритм

  1. Массивтегі әр элементтің есебін сақтайтын хэш кесте жасаңыз.
  2. I-ге массивті 0-ден n-1 аралығында өзгертіңіз
    1. Егер arr [i] k-arr [i] -ге тең болса, онда жауапқа (count_of (k-arr [i]) - 1) қосыңыз.
    2. Егер arr [i] k-arr [i] -ге тең болмаса, онда жауапқа (count_of (k-arr [i]) қосыңыз.
  3. Жауапты қайтарыңыз.

мысал

= {1, 2, 3, 3, 4, 1, 1} массиві үшін құрылған кесте:

Берілген сомамен жұптарды санау

Іске асыру

C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> fre;
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        fre[arr[i]]++;
    }
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == k - arr[i])
        {
            answer += (fre[arr[i]] - 1);
        }
        else
        {
            answer += (fre[k - arr[i]]);
        }
    }
    answer /= 2;
    cout << "Number of pairs with the given sum are: "<<answer << endl;
    return 0;
}
6 4
1 2 2 2 3 4
Number of pairs with the given sum are: 4

JAVA бағдарламасы

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        HashMap<Integer, Integer> fre = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            Integer j = fre.get(arr[i]); 
            fre.put(arr[i], (j == null) ? 1 : j + 1); 
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == k - arr[i])
            {
                answer += (fre.get(arr[i]) - 1);
            }
            else
            {
                Integer j = fre.get(k - arr[i]); 
                if(j!=null)
                    answer += j;
            }
        }
        answer /= 2;
    System.out.println("Number of pairs with the given sum are: "+answer);
  }
}

6 7
3 5 6 1 4 4
Number of pairs with the given sum are: 3

Берілген қосындымен санау жұптарының күрделілігін талдау

Уақыт күрделілігі

Біз массивтің үстінен бір рет қайталаймыз, сондықтан уақыттың күрделілігі O (N) құрайды.

Ғарыштың күрделілігі

Біз хэш-кестені жүргіземіз, сондықтан біздің ғарыштық күрделілігіміз O (N).

Әдебиеттер тізімі