Given an array arr[] of N integers, the task is to find all the pairs possible from the given array.
Note:
- (arr[i], arr[i]) is also considered as a valid pair.
- (arr[i], arr[j]) and (arr[j], arr[i]) are considered as two different pairs.
Examples:
Input: arr[] = {1, 2}
Output: (1, 1), (1, 2), (2, 1), (2, 2).
Input: arr[] = {1, 2, 3}
Output: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)
Approach:
In order to find all the possible pairs from the array, we need to traverse the array and select the first element of the pair. Then we need to pair this element with all the elements in the array from index 0 to N-1.
Below is the step by step approach:
- Traverse the array and select an element in each traversal.
- For each element selected, traverse the array with help of another loop and form the pair of this element with each element in the array from the second loop.
- The array in the second loop will get executed from its first element to its last element, i.e. from index 0 to N-1.
- Print each pair formed.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void printPairs(int arr[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << "(" << arr[i] << ", "
<< arr[j] << ")"
<< ", ";
}
}
}
int main()
{
int arr[] = { 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printPairs(arr, n);
return 0;
}
Java
class GFG{
static void printPairs(int arr[], int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print("(" + arr[i]+ ", "
+ arr[j]+ ")"
+ ", ");
}
}
}
public static void main(String[] args)
{
int arr[] = { 1, 2 };
int n = arr.length;
printPairs(arr, n);
}
}
Python3
def printPairs(arr, n):
for i in range(n):
for j in range(n):
print("(",arr[i],",",arr[j],")",end=", ")
arr=[1, 2]
n = len(arr)
printPairs(arr, n)
C#
using System;
class GFG{
static void printPairs(int []arr, int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Console.Write("(" + arr[i]+ ", "
+ arr[j]+ ")"
+ ", ");
}
}
}
public static void Main(string[] args)
{
int []arr = { 1, 2 };
int n = arr.Length;
printPairs(arr, n);
}
}
Javascript
<script>
function printPairs(arr, n)
{
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
document.write("(" + arr[i] + ", "
+ arr[j] + ")"
+ ", ");
}
}
}
var arr = [ 1, 2 ];
var n = arr.length;
printPairs(arr, n);
</script>
Output
(1, 1), (1, 2), (2, 1), (2, 2),
Time Complexity: O(N2)
Auxiliary Space: O(1)
Using Merge Sort
Approach :
During the merge operation in merge sort we can get all the pairs and we can store those pairs into a vector of pairs.
By just making few changes into the merge sort algorithm we can get all the pairs.
C++
#include<bits/stdc++.h>
using namespace std;
void getPairsMerge(int arr[],int l,int r,int mid,vector<pair<int,int>>&p){
int b[l+r+1],i=l,k=l,j=mid+1;
while(i<=mid && j<=r){
if(arr[i]>arr[j]){
b[k]=arr[j];
p.push_back({arr[i],arr[j]});
p.push_back({arr[j],arr[i]});
p.push_back({arr[j],arr[j]});
k++;
j++;
}
else{
p.push_back({arr[i],arr[j]});
p.push_back({arr[j],arr[i]});
p.push_back({arr[i],arr[i]});
b[k]=arr[i];
i++;
k++;
}
}
while(i<=mid){
b[k]=arr[i];
p.push_back({arr[i],arr[i]});
i++;
k++;
}
while(j<=r){
b[k]=arr[j];
p.push_back({arr[j],arr[j]});
j++;
k++;
}
for(int x=l;x<=r;x++){
arr[x]=b[x];
}
}
void getAllPairs(int arr[],int l,int r,vector<pair<int,int>>&p){
if(l<r){
int mid=(l+r)/2;
getAllPairs(arr,l,mid,p);
getAllPairs(arr,mid+1,r,p);
getPairsMerge(arr,l,r,mid,p);
}
}
int main(){
int n=2;
int arr[n]={1,2};
vector<pair<int,int>>p;
getAllPairs(arr,0,n-1,p);
for(auto it:p){
cout<<it.first<<" "<<it.second<<endl;
}
}
Java
import java.util.*;
class GFG {
static void
getPairsMerge(int[] arr, int l, int r, int mid,
ArrayList<ArrayList<Integer> > p)
{
int[] b = new int[l + r + 1];
int i = l, k = l, j = mid + 1;
while (i <= mid && j <= r) {
if (arr[i] > arr[j]) {
b[k] = arr[j];
ArrayList<Integer> a1
= new ArrayList<Integer>();
a1.add(arr[i]);
a1.add(arr[j]);
ArrayList<Integer> a2
= new ArrayList<Integer>();
a2.add(arr[j]);
a2.add(arr[i]);
ArrayList<Integer> a3
= new ArrayList<Integer>();
a3.add(arr[j]);
a3.add(arr[j]);
p.add(a1);
p.add(a2);
p.add(a3);
k++;
j++;
}
else {
ArrayList<Integer> a1
= new ArrayList<Integer>();
a1.add(arr[i]);
a1.add(arr[j]);
ArrayList<Integer> a2
= new ArrayList<Integer>();
a2.add(arr[j]);
a2.add(arr[i]);
ArrayList<Integer> a3
= new ArrayList<Integer>();
a3.add(arr[i]);
a3.add(arr[i]);
p.add(a1);
p.add(a2);
p.add(a3);
b[k] = arr[i];
i++;
k++;
}
}
while (i <= mid) {
b[k] = arr[i];
ArrayList<Integer> a3
= new ArrayList<Integer>();
a3.add(arr[i]);
a3.add(arr[i]);
p.add(a3);
i++;
k++;
}
while (j <= r) {
b[k] = arr[j];
ArrayList<Integer> a3
= new ArrayList<Integer>();
a3.add(arr[j]);
a3.add(arr[j]);
p.add(a3);
j++;
k++;
}
for (int x = l; x <= r; x++) {
arr[x] = b[x];
}
}
static void
getAllPairs(int[] arr, int l, int r,
ArrayList<ArrayList<Integer> > p)
{
if (l < r) {
int mid = (l + r) / 2;
getAllPairs(arr, l, mid, p);
getAllPairs(arr, mid + 1, r, p);
getPairsMerge(arr, l, r, mid, p);
}
}
public static void main(String[] args)
{
int n = 2;
int[] arr = { 1, 2 };
ArrayList<ArrayList<Integer> > p
= new ArrayList<ArrayList<Integer> >();
getAllPairs(arr, 0, n - 1, p);
for (ArrayList<Integer> it : p)
System.out.println(it.get(0) + " " + it.get(1));
}
}
Python3
def getPairsMerge(arr, l, r, mid, p):
b = [0 for _ in range(l + r + 1)]
i=l
k=l
j=mid+1;
while(i<=mid and j<=r):
if(arr[i]>arr[j]):
b[k]=arr[j];
p.append([arr[i],arr[j]]);
p.append([arr[j],arr[i]]);
p.append([arr[j],arr[j]]);
k+= 1;
j+= 1;
else:
p.append([arr[i],arr[j]]);
p.append([arr[j],arr[i]]);
p.append([arr[i],arr[i]]);
b[k]=arr[i];
i+= 1;
k+= 1;
while(i<=mid):
b[k]=arr[i];
p.append([arr[i],arr[i]]);
i+= 1;
k+= 1;
while(j<=r):
b[k]=arr[j];
p.append([arr[j],arr[j]]);
j+= 1;
k+= 1;
for x in range(l, r + 1):
arr[x]=b[x];
def getAllPairs(arr, l, r, p):
if(l<r):
mid=int((l+r)/2);
getAllPairs(arr,l,mid,p);
getAllPairs(arr,mid+1,r,p);
getPairsMerge(arr,l,r,mid,p);
n=2;
arr = [0 for _ in range(n)]
arr[0] = 1;
arr[1] = 2;
p = [];
getAllPairs(arr,0,n-1,p);
for it in p:
print(it[0], it[1])
C#
using System;
using System.Collections.Generic;
class GFG {
static void getPairsMerge(int[] arr, int l, int r,
int mid, List<int[]> p)
{
int[] b = new int[l + r + 1];
int i = l, k = l, j = mid + 1;
while (i <= mid && j <= r) {
if (arr[i] > arr[j]) {
b[k] = arr[j];
p.Add(new[] { arr[i], arr[j] });
p.Add(new[] { arr[j], arr[i] });
p.Add(new[] { arr[j], arr[j] });
k++;
j++;
}
else {
p.Add(new[] { arr[i], arr[j] });
p.Add(new[] { arr[j], arr[i] });
p.Add(new[] { arr[i], arr[i] });
b[k] = arr[i];
i++;
k++;
}
}
while (i <= mid) {
b[k] = arr[i];
p.Add(new[] { arr[i], arr[i] });
i++;
k++;
}
while (j <= r) {
b[k] = arr[j];
p.Add(new[] { arr[j], arr[j] });
j++;
k++;
}
for (int x = l; x <= r; x++) {
arr[x] = b[x];
}
}
static void getAllPairs(int[] arr, int l, int r,
List<int[]> p)
{
if (l < r) {
int mid = (l + r) / 2;
getAllPairs(arr, l, mid, p);
getAllPairs(arr, mid + 1, r, p);
getPairsMerge(arr, l, r, mid, p);
}
}
public static void Main(string[] args)
{
int n = 2;
int[] arr = { 1, 2 };
List<int[]> p = new List<int[]>();
getAllPairs(arr, 0, n - 1, p);
foreach(var it in p)
Console.WriteLine(it[0] + " " + it[1]);
}
}
Javascript
function getPairsMerge(arr, l, r, mid, p)
{
let b = new Array(l+r+1).fill(0);
let i=l,k=l,j=mid+1;
while(i<=mid && j<=r){
if(arr[i]>arr[j]){
b[k]=arr[j];
p.push([arr[i],arr[j]]);
p.push([arr[j],arr[i]]);
p.push([arr[j],arr[j]]);
k++;
j++;
}
else{
p.push([arr[i],arr[j]]);
p.push([arr[j],arr[i]]);
p.push([arr[i],arr[i]]);
b[k]=arr[i];
i++;
k++;
}
}
while(i<=mid){
b[k]=arr[i];
p.push([arr[i],arr[i]]);
i++;
k++;
}
while(j<=r){
b[k]=arr[j];
p.push([arr[j],arr[j]]);
j++;
k++;
}
for(let x=l;x<=r;x++){
arr[x]=b[x];
}
}
function getAllPairs(arr, l, r, p)
{
if(l<r){
let mid= Math.floor((l+r)/2);
getAllPairs(arr,l,mid,p);
getAllPairs(arr,mid+1,r,p);
getPairsMerge(arr,l,r,mid,p);
}
}
let n=2;
let arr = new Array(n).fill(0);
arr[0] = 1;
arr[1] = 2;
let p = [];
getAllPairs(arr,0,n-1,p);
for(var it of p)
console.log(it[0], it[1])
Time Complexity : O (N LogN )
Auxiliary Space: O(l + r)
Last Updated :
13 Sep, 2022
Like Article
Save Article
Дан несортированный массив целых чисел, найти в нем пару с заданной суммой.
Например,
Input:
nums = [8, 7, 2, 5, 3, 1]
target = 10
Output:
Pair found (8, 2)
or
Pair found (7, 3)
Input:
nums = [5, 2, 6, 8, 1, 9]
target = 12
Output: Pair not found
Потренируйтесь в этой проблеме
Существует несколько методов решения этой проблемы с использованием грубой силы, сортировки и хеширования. Они обсуждаются ниже:
1. Использование грубой силы
Наивное решение состоит в том, чтобы рассматривать каждую пару в заданном массиве и возвращаться, если искомая сумма найдена. Этот подход демонстрируется ниже на C, Java и Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <stdio.h> // Наивный метод поиска пары в массиве с заданной суммой void findPair(int nums[], int n, int target) { // рассмотрим каждый элемент, кроме последнего for (int i = 0; i < n — 1; i++) { // начинаем с i-го элемента до последнего элемента for (int j = i + 1; j < n; j++) { // если искомая сумма найдена, выводим ее if (nums[i] + nums[j] == target) { printf(«Pair found (%d, %d)n», nums[i], nums[j]); return; } } } // доходим сюда, если пара не найдена printf(«Pair not found»); } int main(void) { int nums[] = { 8, 7, 2, 5, 3, 1 }; int target = 10; int n = sizeof(nums)/sizeof(nums[0]); findPair(nums, n, target); return 0; } |
Скачать Выполнить код
результат:
Pair found (8, 2)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Main { // Наивный метод поиска пары в массиве с заданной суммой public static void findPair(int[] nums, int target) { // рассмотрим каждый элемент, кроме последнего for (int i = 0; i < nums.length — 1; i++) { // начинаем с i-го элемента до последнего элемента for (int j = i + 1; j < nums.length; j++) { // если искомая сумма найдена, выводим ее if (nums[i] + nums[j] == target) { System.out.printf(«Pair found (%d, %d)», nums[i], nums[j]); return; } } } // доходим сюда, если пара не найдена System.out.println(«Pair not found»); } public static void main (String[] args) { int[] nums = { 8, 7, 2, 5, 3, 1 }; int target = 10; findPair(nums, target); } } |
Скачать Выполнить код
результат:
Pair found (8, 2)
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
# Наивный метод поиска пары в списке с заданной суммой def findPair(nums, target): # учитывает каждый элемент, кроме последнего for i in range(len(nums) — 1): # начинается с i-го элемента до последнего элемента for j in range(i + 1, len(nums)): # если искомая сумма найдена, вывести ее if nums[i] + nums[j] == target: print(‘Pair found’, (nums[i], nums[j])) return # В списке нет пары с указанной суммой print(‘Pair not found’) if __name__ == ‘__main__’: nums = [8, 7, 2, 5, 3, 1] target = 10 findPair(nums, target) |
Скачать Выполнить код
результат:
Pair found (8, 2)
Временная сложность приведенного выше решения равна O(n2) и не требует дополнительного места, где n это размер ввода.
2. Использование сортировки
Идея состоит в том, чтобы отсортировать заданный массив в порядке возрастания и поддерживать пространство поиска, сохраняя два индекса (low а также high), который изначально указывает на две конечные точки массива. Затем уменьшите область поиска nums[low…high] на каждой итерации цикла путем сравнения суммы элементов, присутствующих в индексах low а также high с желаемой суммой. Увеличение low если сумма меньше ожидаемой суммы; в противном случае уменьшить high если сумма больше желаемой суммы. Если пара найдена, вернуть ее.
Ниже приведена реализация C++, Java и Python, основанная на идее:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <algorithm> using namespace std; // Функция поиска пары в массиве с заданной суммой с помощью сортировки void findPair(int nums[], int n, int target) { // сортируем массив по возрастанию sort(nums, nums + n); // поддерживать два индекса, указывающих на конечные точки массива int low = 0; int high = n — 1; // уменьшаем пространство поиска `nums[low…high]` на каждой итерации цикла // цикл до тех пор, пока пространство поиска не будет исчерпано while (low < high) { // сумма найдена if (nums[low] + nums[high] == target) { cout << «Pair found (« << nums[low] << «, « << nums[high] << «)n»; return; } // увеличиваем `low` индекс, если сумма меньше желаемой суммы; // уменьшаем индекс `high`, если сумма больше желаемой суммы (nums[low] + nums[high] < target)? low++: high—; } // доходим сюда, если пара не найдена cout << «Pair not found»; } int main() { int nums[] = { 8, 7, 2, 5, 3, 1 }; int target = 10; int n = sizeof(nums)/sizeof(nums[0]); findPair(nums, n, target); return 0; } |
Скачать Выполнить код
результат:
Pair found (2, 
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.Arrays; class Main { // Функция поиска пары в массиве с заданной суммой с помощью сортировки public static void findPair(int[] nums, int target) { // сортируем массив по возрастанию Arrays.sort(nums); // поддерживать два индекса, указывающих на конечные точки массива int low = 0; int high = nums.length — 1; // уменьшаем пространство поиска `nums[low…high]` на каждой итерации цикла // цикл до тех пор, пока пространство поиска не будет исчерпано while (low < high) { // сумма найдена if (nums[low] + nums[high] == target) { System.out.printf(«Pair found (%d, %d)», nums[low], nums[high]); return; } // увеличиваем `low` индекс, если сумма меньше желаемой суммы; // уменьшаем индекс `high`, если сумма больше желаемой суммы if (nums[low] + nums[high] < target) { low++; } else { high—; } } // доходим сюда, если пара не найдена System.out.println(«Pair not found»); } public static void main (String[] args) { int[] nums = { 8, 7, 2, 5, 3, 1 }; int target = 10; findPair(nums, target); } } |
Скачать Выполнить код
результат:
Pair found (2,
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Функция поиска пары в массиве с заданной суммой с помощью сортировки def findPair(nums, target): # сортирует список по возрастанию nums.sort() # поддерживает два индекса, указывающих на конечные точки списка (low, high) = (0, len(nums) — 1) # уменьшает пространство поиска `nums[low…high]` на каждой итерации цикла # Цикл # до тех пор, пока пространство поиска не будет исчерпано while low < high: if nums[low] + nums[high] == target: # Цель # найдена print(‘Pair found’, (nums[low], nums[high])) return # увеличивает `low` индекс, если общая сумма меньше желаемой суммы; # уменьшает `high` индекс, если сумма больше желаемой суммы if nums[low] + nums[high] < target: low = low + 1 else: high = high — 1 # Пара с указанной суммой не существует print(‘Pair not found’) if __name__ == ‘__main__’: nums = [8, 7, 2, 5, 3, 1] target = 10 findPair(nums, target) |
Скачать Выполнить код
результат:
Pair found (2,
Временная сложность приведенного выше решения равна O(n.log(n)) и не требует дополнительного места.
3. Использование хеширования
Мы можем использовать хеш-таблица решить эту задачу за линейное время. Идея состоит в том, чтобы вставить каждый элемент массива nums[i] в карту. Мы также проверяем, есть ли разница (nums[i], target - nums[i]) уже есть на карте или нет. Если разница видна раньше, напечатайте пару и вернитесь. Алгоритм может быть реализован следующим образом на C++, Java и Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <unordered_map> using namespace std; // Функция поиска пары в массиве с заданной суммой с использованием хеширования void findPair(int nums[], int n, int target) { // создаем пустую карту unordered_map<int, int> map; // делаем для каждого элемента for (int i = 0; i < n; i++) { // проверяем, существует ли пара (nums[i], target — nums[i]) // если разница была видна раньше, выводим пару if (map.find(target — nums[i]) != map.end()) { cout << «Pair found (« << nums[map[target — nums[i]]] << «, « << nums[i] << «)n»; return; } // сохраняем индекс текущего элемента на карте map[nums[i]] = i; } // доходим сюда, если пара не найдена cout << «Pair not found»; } int main() { int nums[] = { 8, 7, 2, 5, 3, 1 }; int target = 10; int n = sizeof(nums)/sizeof(nums[0]); findPair(nums, n, target); return 0; } |
Скачать Выполнить код
результат:
Pair found (8, 2)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import java.util.HashMap; import java.util.Map; class Main { // Функция поиска пары в массиве с заданной суммой с использованием хеширования public static void findPair(int[] nums, int target) { // создаем пустой HashMap Map<Integer, Integer> map = new HashMap<>(); // делаем для каждого элемента for (int i = 0; i < nums.length; i++) { // проверяем, существует ли пара (nums[i], target-nums[i]) // если разница была видна раньше, выводим пару if (map.containsKey(target — nums[i])) { System.out.printf(«Pair found (%d, %d)», nums[map.get(target — nums[i])], nums[i]); return; } // сохраняем индекс текущего элемента на карте map.put(nums[i], i); } // доходим сюда, если пара не найдена System.out.println(«Pair not found»); } public static void main (String[] args) { int[] nums = { 8, 7, 2, 5, 3, 1 }; int target = 10; findPair(nums, target); } } |
Скачать Выполнить код
результат:
Pair found (8, 2)
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
# Функция поиска пары в массиве с заданной суммой с использованием хеширования def findPair(nums, target): # создать пустой словарь d = {} # делаем на каждый элемент for i, e in enumerate(nums): # проверяет, существует ли пара (e, target — e) #, если разница была видна раньше, вывести пару if target — e in d: print(‘Pair found’, (nums[d.get(target — e)], nums[i])) return # сохраняет индекс текущего элемента в словаре d[e] = i # В списке нет пары с указанной суммой print(‘Pair not found’) if __name__ == ‘__main__’: nums = [8, 7, 2, 5, 3, 1] target = 10 findPair(nums, target) |
Скачать Выполнить код
результат:
Pair found (8, 2)
Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n это размер ввода.
Упражнение: Расширьте решение, чтобы вывести все пары в массиве, имеющие заданную сумму.
Похожие сообщения:
Найти тройку с заданной суммой в массиве
4–Суммированная задача | Четверки с заданной суммой
Найдите пару с заданной суммой в BST
Если имеется, к примеру массив вида { 10, 10, 10, 10, 20, 20 }, то count после цикла будет равно 4, и вы получите, что имеется только 2 пары равных элементов, используя формулу count /= 2.. На самом деле правильно было бы считать 10, 10, 10, 10 == 3 Затем ( 3 + 1 ) / 2 == 2. То же самое и здесь 20, 20 == 1, ( 1 + 1 ) / 2 = 1.
При вашем подсчете, вы теряете остаток от деления на 2 для каждого числа одинаковых чисел.
Могу предложить следующее решение
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = { 10, 20, 20, 10, 10, 30, 50, 10, 20 };
std::sort( v.begin(), v.end() );
std::vector<int>::size_type count = 0;
for ( std::vector<int>::size_type i = 0; ++i < v.size(); )
{
if ( v[i] == v[i-1] )
{
++i; ++count;
}
}
std::cout << "count = " << count << std::endl;
return 0;
}
Для заданного массива вывод на консоль программы будет таким
count = 3
Эту задачу можно решить двумя способами. Выбор определяется компромиссом между эффективностью использования времени, памяти или сложностью кода.
Простое решение
Очень простое и эффективное (по времени) решение — создание хэш-таблицы, отображающей целое число в целое число. Данный алгоритм работает, пошагово проходя весь массив. Для каждого элемента x в хэш-таблице ищется sum – x и, если запись существует, выводится (x, sum — x). После этого x добавляется в таблицу и проверяется следующий элемент.
Альтернативное решение
Давайте начнем с формулировки. Если мы попытаемся найти пару чисел, сумма которых равна z, то дополнение будет z – x (величина, которую нужно добавить к x, что бы получить z). Если мы попытаемся найти пару чисел, при суммировании которых получается 12, дополнением к -5 будет число 17.
Представьте, что у нас есть отсортированный массив {-2, -1, 0, 3, 5, 6, 7, 9, 13, 14}. Пусть first указывает на начало массива, а last — на его конец. Чтобы найти дополнение к first, мы двигаем last назад, пока не найдем искомую величину. Если first + last < sum, то дополнения к first не существует. Можно также перемещать first на встречу к last. Тогда мы остановимся, если first окажется больше, чем last.
Почему такое решение найдет все дополнения к first? Поскольку массив отсортирован, мы проверяем меньшие числа. Когда first + last меньше sum, нет смысла проверять меньшие значения, они не помогут найти дополнение.
Почему данное решение найдет все дополнения last? Потому что все пары формируются с помощью first и last. Мы нашли все дополнения first, а значит, нашли все дополнения last.
void printPairSums (int[] array, int sum) {
Arrays.sort(array);
int first = 0;
int last = array.length - 1;
while (first < last) {
int s = array[first] + array[last];
if (s == sum) {
System.out.printIn(array[first] + "" + array[last]);
first++;
last--;
} else {
if (s < sum) first++;
else last--;
}
}
}
Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»
Из всех пар элементов, равноудаленных от начала и конца одномерного массива A(M), найдите пару элементов, имеющих наибольшую сумму. Если элемент не имеет пары, то он не рассматривается. Выход. данные: [индекс элемента массива A из пары] [пробел] [индекс другого элемента массива A из пары]
Как доделать или переделать код?
| C | ||
|