Рубрики

Подсчитать пары с заданной суммой

Для данного массива целых чисел и числа «сумма» найдите количество пар целых чисел в массиве, сумма которых равна «сумме».

Примеры:

Input  :  arr[] = {1, 5, 7, -1}, 
          sum = 6
Output :  2
Pairs with sum 6 are (1, 5) and (7, -1)

Input  :  arr[] = {1, 5, 7, -1, 5}, 
          sum = 6
Output :  3
Pairs with sum 6 are (1, 5), (7, -1) &
                     (1, 5)         

Input  :  arr[] = {1, 1, 1, 1}, 
          sum = 2
Output :  6
There are 3! pairs with sum 2.

Input  :  arr[] = {10, 12, 10, 15, -1, 7, 6, 
                   5, 4, 2, 1, 1, 1}, 
          sum = 11
Output :  9

Ожидаемая сложность времени O (n)

Простое решение — обойти каждый элемент и проверить, есть ли в массиве другое число, которое можно добавить к нему, чтобы получить сумму.

C ++

// C ++ реализация простого метода для поиска количества
// пары с заданной суммой.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество пар в arr [0..n-1] с суммой, равной
// подвести'

int getPairsCount(int arr[], int n, int sum)

{

    int count = 0; // Инициализировать результат

  

    // Рассмотрим все возможные пары и проверяем их суммы

    for (int i=0; i<n; i++)

        for (int j=i+1; j<n; j++)

            if (arr[i]+arr[j] == sum)

                count++;

  

    return count;

}

  
// Функция драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {1, 5, 7, -1, 5} ;

    int n = sizeof(arr)/sizeof(arr[0]);

    int sum = 6;

    cout << "Count of pairs is " 

         << getPairsCount(arr, n, sum);

    return 0;

}

Джава

// Java реализация простого метода для поиска количества
// пары с заданной суммой.

public class find

{

    public static void main(String args[])

    {

        int[] arr = { 1, 5, 7, -1, 5 };

        int sum = 6;

        getPairsCount(arr, sum);

    }

  

    // Печатает количество пар в arr [0..n-1] с суммой, равной

    // подвести'

    public static void getPairsCount(int[] arr, int sum)

    {

  

        int count = 0;// Инициализировать результат

  

        // Рассмотрим все возможные пары и проверяем их суммы

        for (int i = 0; i < arr.length; i++)

            for (int j = i + 1; j < arr.length; j++)

                if ((arr[i] + arr[j]) == sum)

                    count++;

  

        System.out.printf("Count of pairs is %d",count);

    }

}
// Эта программа предоставлена Jyotsna

python3

# Python3 реализация простого метода
# найти количество пар с заданной суммой.

  
# Возвращает количество пар в arr [0..n-1]
# с суммой, равной 'сумме'

def getPairsCount(arr, n, sum):

      

    count = 0 # Инициализировать результат

  

    # Рассмотрим все возможные пары

    # и проверьте их суммы

    for i in range(0, n):

        for j in range(i + 1, n):

            if arr[i] + arr[j] == sum:

                count += 1

      

    return count

  
# Функция драйвера

arr = [1, 5, 7, -1, 5]

n = len(arr)

sum = 6

print("Count of pairs is",

      getPairsCount(arr, n, sum))

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # реализация простого
// метод для определения количества
// пары с заданной суммой.

using System;

  

class GFG

{

public static void getPairsCount(int[] arr,

                                 int sum) 

  

    int count = 0; // Инициализировать результат

  

    // Рассмотрим все возможные пары

    // и проверяем их суммы

    for (int i = 0; 

             i < arr.Length; i++) 

        for (int j = i + 1; 

                 j < arr.Length; j++) 

            if ((arr[i] + arr[j]) == sum) 

                count++; 

  

    Console.WriteLine("Count of pairs is "

                                     count); 

  
// Код драйвера

static public void Main ()

{

    int[] arr = { 1, 5, 7, -1, 5 }; 

    int sum = 6; 

    getPairsCount(arr, sum); 

}
}

  
// Этот код добавлен
// по Sach_Code

PHP

<?php
// простая реализация PHP
// метод для определения количества
// пары с заданной суммой.

  
// Возвращает количество пар в
// arr [0..n-1] с суммой, равной
// подвести'

function getPairsCount($arr, $n, $sum)

{

    // Инициализировать результат

    $count = 0; 

  

    // Рассмотрим все возможные пары

    // и проверяем их суммы

    for ($i = 0; $i < $n; $i++)

        for ($j = $i + 1; $j < $n; $j++)

            if ($arr[$i] + $arr[$j] == $sum)

                $count++;

  

    return $count;

}

  

    // Код драйвера

    $arr = array(1, 5, 7, -1, 5) ;

    $n = sizeof($arr);

    $sum = 6;

    echo "Count of pairs is "

         , getPairsCount($arr, $n, $sum);

           
// Этот код предоставлен нитин митталь.
?>


Выход :

Count of pairs is 3

Сложность времени: O (n 2 )
Вспомогательное пространство: O (1)

Лучшее решение возможно за время O (n) .

Ниже приведен алгоритм.

  1. Создайте карту для хранения частоты каждого числа в массиве. (Требуется одиночный обход)
  2. В следующем обходе для каждого элемента проверьте, можно ли его объединить с любым другим элементом (кроме самого себя!), Чтобы получить желаемую сумму. Увеличьте счетчик соответственно.
  3. После завершения второго обхода у нас в счетчике будет вдвое больше необходимого значения, потому что каждая пара считается два раза. Следовательно, разделите счет на 2 и верните.

Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ реализация простого метода для поиска количества
// пары с заданной суммой.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество пар в arr [0..n-1] с суммой, равной
// подвести'

int getPairsCount(int arr[], int n, int sum)

{

    unordered_map<int, int> m;

  

    // Сохраняем количество всех элементов на карте m

    for (int i=0; i<n; i++)

        m[arr[i]]++;

  

    int twice_count = 0;

  

    // перебираем каждый элемент и увеличиваем

    // считать (обратите внимание, что каждая пара учитывается дважды)

    for (int i=0; i<n; i++)

    {

        twice_count += m[sum-arr[i]];

  

        // если пара (arr [i], arr [i]) удовлетворяет условию,

        // тогда мы должны убедиться, что счет

        // уменьшилось на одно такое, что (arr [i], arr [i])

        // пара не считается

        if (sum-arr[i] == arr[i])

            twice_count--;

    }

  

    // вернуть половину double_count

    return twice_count/2;

}

  
// Функция драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {1, 5, 7, -1, 5} ;

    int n = sizeof(arr)/sizeof(arr[0]);

    int sum = 6;

    cout << "Count of pairs is " 

         << getPairsCount(arr, n, sum);

    return 0;

}

Джава

/ * Java-реализация простого метода для определения количества
пары с заданной суммой * /

  

import java.util.HashMap;

  

class Test

{

    static int arr[] = new int[]{1, 5, 7, -1, 5} ;

      

    // Возвращает количество пар в arr [0..n-1] с суммой, равной

    // подвести'

    static int getPairsCount(int n, int sum)

    {

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

  

        // Сохраняем количество всех элементов в карте hm

        for (int i=0; i<n; i++){

              

            // установка значения в 0, если ключ не найден

            if(!hm.containsKey(arr[i]))

                hm.put(arr[i],0);

                  

            hm.put(arr[i], hm.get(arr[i])+1);

        }

        int twice_count = 0;

  

        // перебираем каждый элемент и увеличиваем

        // считать (обратите внимание, что каждая пара учитывается дважды)

        for (int i=0; i<n; i++)

        {

            if(hm.get(sum-arr[i]) != null)

                twice_count += hm.get(sum-arr[i]);

  

            // если пара (arr [i], arr [i]) удовлетворяет условию,

            // тогда мы должны убедиться, что счет

            // уменьшилось на одно такое, что (arr [i], arr [i])

            // пара не считается

            if (sum-arr[i] == arr[i])

                twice_count--;

        }

  

        // вернуть половину double_count

        return twice_count/2;

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) {

          

        int sum = 6;

        System.out.println("Count of pairs is "

                            getPairsCount(arr.length,sum));

          

    }

}
// Этот код предоставлен Gaurav Miglani

python3

# Python 3 реализация простого метода
# найти количество пар с заданной суммой.

import sys

  
# Возвращает количество пар в arr [0..n-1]
# с суммой, равной 'сумме'

def getPairsCount(arr, n, sum):

      

    m = [0] * 1000

      

    # Хранить счетчики всех элементов на карте m

    for i in range(0, n):

        m[arr[i]]

        m[arr[i]] += 1

  

    twice_count = 0

  

    # Перебирать каждый элемент и увеличивать

    # количество (обратите внимание, что каждая пара

    # посчитано дважды)

    for i in range(0, n):

      

        twice_count += m[sum - arr[i]] 

  

        # if (arr [i], arr [i]) пара удовлетворяет

        # условие, то мы должны убедиться, что

        # количество уменьшается на один такой

        # что пара (arr [i], arr [i]) не является

        # считается

        if (sum - arr[i] == arr[i]):

            twice_count -= 1

      

    # вернуть половину double_count

    return int(twice_count / 2

  
# Функция драйвера

arr = [1, 5, 7, -1, 5

n = len(arr)

sum = 6

  

print("Count of pairs is", getPairsCount(arr,

                                     n, sum))

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # реализация простого метода для
// найти количество пар с заданной суммой

using System;

using System.Collections.Generic;

  

class GFG

{

public static int[] arr = new int[]{1, 5, 7, -1, 5};

  
// Возвращает количество пар в arr [0..n-1]
// с суммой, равной 'сумме'

public static int getPairsCount(int n, int sum)

{

    Dictionary<int

               int> hm = new Dictionary<int

                                        int>();

  

    // Сохраняем количество всех элементов

    // в карте хм

    for (int i = 0; i < n; i++)

    {

  

        // инициализация значения до 0,

        // если ключ не найден

        if (!hm.ContainsKey(arr[i]))

        {

            hm[arr[i]] = 0;

        }

  

        hm[arr[i]] = hm[arr[i]] + 1;

    }

    int twice_count = 0;

  

    // перебираем каждый элемент и

    // увеличить счетчик (обратите внимание, что

    // каждая пара учитывается дважды)

    for (int i = 0; i < n; i++)

    {

        if (hm[sum - arr[i]] != null)

        {

            twice_count += hm[sum - arr[i]];

        }

  

        // если пара (arr [i], arr [i]) удовлетворяет

        // условие, то нам нужно обеспечить

        // что количество уменьшается на один

        // такой, что (arr [i], arr [i])

        // пара не считается

        if (sum - arr[i] == arr[i])

        {

            twice_count--;

        }

    }

  

    // вернуть половину double_count

    return twice_count / 2;

}

  
// Код драйвера

public static void Main(string[] args)

{

    int sum = 6;

    Console.WriteLine("Count of pairs is "

                       getPairsCount(arr.Length, sum));

}
}

  
// Этот код предоставлен Shrikant13


Выход :

Count of pairs is 3

Эта статья предоставлена Ашутошем Кумаром . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитать пары с заданной суммой

0.00 (0%) 0 votes