Dada una array desordenada de enteros. La tarea es encontrar dos pares que no se superpongan cuya suma sea igual.
Se dice que dos pares no se superponen si todos los elementos de los pares tienen índices diferentes. Es decir, se dice que el par (A i , A j ) y el par (A m , A n ) no se superponen si i ≠ j ≠ m ≠ n .
Ejemplos :
Input: arr[] = {8, 4, 7, 8, 4}
Output: Pair First(4, 8)
Pair Second (8, 4)
Input: arr[] = {8, 4, 7, 4}
Output: No such non-overlapping pairs present.
Note: (8, 4) and (8, 4) forms overlapping pair
as index of 8 is same in both pairs.
La idea es utilizar un mapa de pares clave-valor para almacenar todas las ocurrencias de una suma. La clave en el mapa almacenará la suma y el valor correspondiente será una lista de pares de índices (i, j) con esa suma.
- La idea es atravesar la array y generar todos los pares posibles.
- Si se encuentra una nueva suma, insértela directamente en el mapa; de lo contrario, verifique si alguno de los pares encontrados anteriormente con esa suma no se superpone con el par actual.
- Si no, imprima ambos pares.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ programs to find two non-overlapping
// pairs having equal sum in an Array
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
typedef pair<int, int> Pair;
// Function to find two non-overlapping
// with same sum in an array
void findPairs(int arr[], int n)
{
// first create an empty map
// key -> which is sum of a pair of
// elements in the array
// value -> vector storing index of
// every pair having that sum
unordered_map<int, vector<Pair> > map;
// consider every pair (arr[i], arr[j])
// and where (j > i)
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// calculate sum of current pair
int sum = arr[i] + arr[j];
// if sum is already present in the map
if (map.find(sum) != map.end()) {
// check every pair having equal sum
for (auto pair : map.find(sum)->second) {
int m = pair.first, n = pair.second;
// if pairs don't overlap,
// print them and return
if ((m != i && m != j) && (n != i && n != j)) {
cout << "Pair First(" << arr[i] << ", "
<< arr[j] << ")\nPair Second ("
<< arr[m] << ", " << arr[n] << ")";
return;
}
}
}
// Insert current pair into the map
map[sum].push_back({ i, j });
}
}
// If no such pair found
cout << "No such non-overlapping pairs present";
}
// Driver Code
int main()
{
int arr[] = { 8, 4, 7, 8, 4 };
int size = sizeof(arr) / sizeof(arr[0]);
findPairs(arr, size);
return 0;
}
Java
// Java program to find two non-overlapping
// pairs having equal sum in an Array
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
// Declare a pair
class Pair {
public int x, y;
Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
class GFG {
// Function to find two non-overlapping
// pairs with same sum in an array
public static void findPairs(int[] A)
{
// first create an empty map
// key -> which is sum of a pair
// of elements in the array
// value -> list storing index of
// every pair having that sum
Map<Integer, List<Pair> > map = new HashMap<>();
// consider every pair (A[i], A[j]) where (j > i)
for (int i = 0; i < A.length - 1; i++) {
for (int j = i + 1; j < A.length; j++) {
// calculate sum of current pair
int sum = A[i] + A[j];
// if sum is already present in the map
if (map.containsKey(sum)) {
// check every pair having desired sum
for (Pair pair : map.get(sum)) {
int x = pair.x;
int y = pair.y;
// if pairs don't overlap, print
// them and return
if ((x != i && x != j) && (y != i && y != j)) {
System.out.println("Pair First(" + A[i] + ", "
+ A[j] + ")");
System.out.println("Pair Second (" + A[x] + ", "
+ A[y] + ")");
return;
}
}
}
// Insert current pair into the map
map.putIfAbsent(sum, new ArrayList<>());
map.get(sum).add(new Pair(i, j));
}
}
System.out.print("No such non-overlapping pairs present");
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 8, 4, 7, 8, 4 };
findPairs(A);
}
}
Python3
# Python3 programs to find two non-overlapping
# pairs having equal Sum in an Array
# Function to find two non-overlapping
# with same Sum in an array
def findPairs(arr, size):
# first create an empty Map
# key -> which is Sum of a pair of
# elements in the array
# value -> vector storing index of
# every pair having that Sum
Map = {}
# consider every pair (arr[i], arr[j])
# and where (j > i)
for i in range(0, size - 1):
for j in range(i + 1, size):
# calculate Sum of current pair
Sum = arr[i] + arr[j]
# if Sum is already present in the Map
if Sum in Map:
# check every pair having equal Sum
for pair in Map[Sum]:
m, n = pair
# if pairs don't overlap,
# print them and return
if ((m != i and m != j) and
(n != i and n != j)):
print("Pair First ({}, {})".
format(arr[i], arr[j]))
print("Pair Second ({}, {})".
format(arr[m], arr[n]))
return
# Insert current pair into the Map
if Sum not in Map:
Map[Sum] = []
Map[Sum].append((i, j))
# If no such pair found
print("No such non-overlapping pairs present")
# Driver Code
if __name__ == "__main__":
arr = [8, 4, 7, 8, 4]
size = len(arr)
findPairs(arr, size)
# This code is contributed by Rituraj Jain
C#
// C# program to find two non-overlapping
// pairs having equal sum in an Array
using System;
using System.Collections.Generic;
// Declare a pair
class Pair
{
public int x, y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
class GFG{
// Function to find two non-overlapping
// pairs with same sum in an array
public static void findPairs(int[] A)
{
// First create an empty map
// key -> which is sum of a pair
// of elements in the array
// value -> list storing index of
// every pair having that sum
Dictionary<int,
List<Pair>> map = new Dictionary<int,
List<Pair>>();
// Consider every pair (A[i], A[j])
// where (j > i)
for(int i = 0; i < A.Length - 1; i++)
{
for(int j = i + 1; j < A.Length; j++)
{
// Calculate sum of current pair
int sum = A[i] + A[j];
// If sum is already present in the map
if (map.ContainsKey(sum))
{
// Check every pair having desired sum
foreach(Pair pair in map[sum])
{
int x = pair.x;
int y = pair.y;
// If pairs don't overlap, print
// them and return
if ((x != i && x != j) &&
(y != i && y != j))
{
Console.WriteLine("Pair First(" + A[i] +
", " + A[j] + ")");
Console.WriteLine("Pair Second (" + A[x] +
", " + A[y] + ")");
return;
}
}
}
// Insert current pair into the map
map[sum] = new List<Pair>();
map[sum].Add(new Pair(i, j));
}
}
Console.Write("No such non-overlapping pairs present");
}
// Driver Code
public static void Main(String[] args)
{
int[] A = { 8, 4, 7, 8, 4 };
findPairs(A);
}
}
// This code is contributed by Princi Singh
Producción:
Pair First(4, 8) Pair Second (8, 4)