Contar pares con suma dada | conjunto 2

Dada una array arr[] y una suma de enteros , la tarea es encontrar el número de pares de enteros en la array cuya suma es igual a sum .
Ejemplos: 
 

Entrada: arr[] = {1, 5, 7, -1}, suma = 6 
Salida: 2 
pares con suma 6 son (1, 5) y (7, -1)
Entrada: arr[] = {1, 5 , 7, -1, 5}, suma = 6 
Salida: 3 
pares con suma 6 son (1, 5), (7, -1) y (1, 5) 
Entrada: arr[] = {1, 1, 1 , 1}, suma = 2 
Salida: 6 
 

Enfoque: Ya se han discutido dos métodos diferentes aquí . Aquí, se discutirá  un método basado en la clasificación .
 

1. Ordene la array y tome dos punteros i y j , un puntero que apunta al inicio de la array, es decir, i = 0 y otro puntero que apunta al final de la array, es decir, j = n – 1 .
2. • Mayor que la suma entonces decremento j .
   • Menor que la suma entonces incremente i .
   • Es igual a la suma y luego cuenta tales pares.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of pairs
// from arr[] with the given sum
int pairs_count(int arr[], int n, int sum)
{
    // To store the count of pairs
    int ans = 0;
 
    // Sort the given array
    sort(arr, arr + n);
 
    // Take two pointers
    int i = 0, j = n - 1;
 
    while (i < j) {
        // If sum is greater
        if (arr[i] + arr[j] < sum)
            i++;
 
        // If sum is lesser
        else if (arr[i] + arr[j] > sum)
            j--;
 
        // If sum is equal
        else {
            // Find the frequency of arr[i]
            int x = arr[i], xx = i;
            while (i < j and arr[i] == x)
                i++;
 
            // Find the frequency of arr[j]
            int y = arr[j], yy = j;
            while (j >= i and arr[j] == y)
                j--;
 
            // If arr[i] and arr[j] are same
            // then remove the extra number counted
            if (x == y) {
                int temp = i - xx + yy - j - 1;
                ans += (temp * (temp + 1)) / 2;
            }
            else
                ans += (i - xx) * (yy - j);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 5, 7, 5, -1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 6;
 
    cout << pairs_count(arr, n, sum);
 
    return 0;
}

//Java implementation of the approach
import java.util.Arrays;
import java.io.*;
 
class GFG
{
     
// Function to return the count of pairs
// from arr[] with the given sum
static int pairs_count(int arr[], int n, int sum)
{
    // To store the count of pairs
    int ans = 0;
 
    // Sort the given array
    Arrays.sort(arr);
 
    // Take two pointers
    int i = 0, j = n - 1;
 
    while (i < j)
    {
         
        // If sum is greater
        if (arr[i] + arr[j] < sum)
            i++;
 
        // If sum is lesser
        else if (arr[i] + arr[j] > sum)
            j--;
 
        // If sum is equal
        else
        {
             
            // Find the frequency of arr[i]
            int x = arr[i], xx = i;
            while ((i < j ) && (arr[i] == x))
                i++;
 
            // Find the frequency of arr[j]
            int y = arr[j], yy = j;
            while ((j >= i )&& (arr[j] == y))
                j--;
 
            // If arr[i] and arr[j] are same
            // then remove the extra number counted
            if (x == y)
            {
                int temp = i - xx + yy - j - 1;
                ans += (temp * (temp + 1)) / 2;
            }
            else
                ans += (i - xx) * (yy - j);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 5, 7, 5, -1 };
    int n = arr.length;
    int sum = 6;
     
    System.out.println (pairs_count(arr, n, sum));
}
}
 
// The code is contributed by ajit..

# Python3 implementation of the approach
 
# Function to return the count of pairs
# from arr with the given sum
def pairs_count(arr, n, sum):
     
    # To store the count of pairs
    ans = 0
 
    # Sort the given array
    arr = sorted(arr)
 
    # Take two pointers
    i, j = 0, n - 1
 
    while (i < j):
         
        # If sum is greater
        if (arr[i] + arr[j] < sum):
            i += 1
 
        # If sum is lesser
        elif (arr[i] + arr[j] > sum):
            j -= 1
             
        # If sum is equal
        else:
             
            # Find the frequency of arr[i]
            x = arr[i]
            xx = i
            while (i < j and arr[i] == x):
                i += 1
 
            # Find the frequency of arr[j]
            y = arr[j]
            yy = j
            while (j >= i and arr[j] == y):
                j -= 1
 
            # If arr[i] and arr[j] are same
            # then remove the extra number counted
            if (x == y):
                temp = i - xx + yy - j - 1
                ans += (temp * (temp + 1)) // 2
            else:
                ans += (i - xx) * (yy - j)
 
    # Return the required answer
    return ans
 
# Driver code
arr = [1, 5, 7, 5, -1]
n = len(arr)
sum = 6
 
print(pairs_count(arr, n, sum))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
     
class GFG
{
     
// Function to return the count of pairs
// from arr[] with the given sum
static int pairs_count(int []arr,
                       int n, int sum)
{
    // To store the count of pairs
    int ans = 0;
 
    // Sort the given array
    Array.Sort(arr);
 
    // Take two pointers
    int i = 0, j = n - 1;
 
    while (i < j)
    {
         
        // If sum is greater
        if (arr[i] + arr[j] < sum)
            i++;
 
        // If sum is lesser
        else if (arr[i] + arr[j] > sum)
            j--;
 
        // If sum is equal
        else
        {
             
            // Find the frequency of arr[i]
            int x = arr[i], xx = i;
            while ((i < j) && (arr[i] == x))
                i++;
 
            // Find the frequency of arr[j]
            int y = arr[j], yy = j;
            while ((j >= i) && (arr[j] == y))
                j--;
 
            // If arr[i] and arr[j] are same
            // then remove the extra number counted
            if (x == y)
            {
                int temp = i - xx + yy - j - 1;
                ans += (temp * (temp + 1)) / 2;
            }
            else
                ans += (i - xx) * (yy - j);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void Main (String[] args)
{
    int []arr = { 1, 5, 7, 5, -1 };
    int n = arr.Length;
    int sum = 6;
     
    Console.WriteLine (pairs_count(arr, n, sum));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of pairs
// from arr[] with the given sum
function pairs_count(arr, n, sum)
{
    // To store the count of pairs
    let ans = 0;
 
    // Sort the given array
    arr.sort();
 
    // Take two pointers
    let i = 0, j = n - 1;
 
    while (i < j) {
        // If sum is greater
        if (arr[i] + arr[j] < sum)
            i++;
 
        // If sum is lesser
        else if (arr[i] + arr[j] > sum)
            j--;
 
        // If sum is equal
        else {
            // Find the frequency of arr[i]
            let x = arr[i], xx = i;
            while (i < j && arr[i] == x)
                i++;
 
            // Find the frequency of arr[j]
            let y = arr[j], yy = j;
            while (j >= i && arr[j] == y)
                j--;
 
            // If arr[i] and arr[j] are same
            // then remove the extra number counted
            if (x == y) {
                let temp = i - xx + yy - j - 1;
                ans += (temp * (temp + 1)) / 2;
            }
            else
                ans += (i - xx) * (yy - j);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
    let arr = [ 1, 5, 7, 5, -1 ];
    let n = arr.length;
    let sum = 6;
 
    document.write(pairs_count(arr, n, sum));
 
// This code is contributed by Mayank Tyagi
 
</script>

3

Complejidad de tiempo: O(n * log n)

Espacio Auxiliar: O(1)