给定两个未排序的数组,找到所有总和为x的对


难度级别 易得奖学金
经常问 亚马逊 Facebook
排列 哈希 哈希

问题陈述

给出两个未分类 数组,找到所有总和为x的对,表示您得到了两个未排序的整数数组和一个名为sum的值的问题。 问题语句要求找出对的总数,并打印所有这些对,它们加起来等于给定值sum(总和)。

使用案列

arr1[] = { 3,6,1,4,8,2}

arr2[] = { 2,1,5,7,2,4}

sum = 9
(8, 1), (4, 5) (2, 7)

说明:所有三个对都有一个数字,该数字的总和等于给定值9。

arr1[] = { 2,5,1,7,9}

arr2[] = { 3,6,8,1,0}

sum = 7
(1, 6), (7, 0)

说明:两对都具有一个数字,该数字的总和等于给定值7。

在两个未排序的数组中查找具有sum = x的所有对的算法

1. Declare a Set.
2. Insert all the values of array1 into the Set.
3. Traverse the array2.
4. Check if the difference of sum and each number of array2 is present in a set.
5. If present then prints the difference and the current array element.

说明

给定两个未排序的数组,找到总和为x的所有对。 为此,我们将使用该集合。 集合还提供了删除常见元素的功能。 我们要做的是将所有array1的值插入到集合中。 在这里,如果set删除或不删除元素。 我们不太在乎,因为我们只需要数字来检查该对是否可以形成。

在遍历第一个数组时,我们将把它的所有值插入到集合中。 后来,有了这个集合,我们将发现是否可以形成任何对,它们的总和等于给定值,称为和。 完成将所有值插入集合后,将遍历数组2。

从第二个数组的第一个元素开始,我们将在遍历时检查给定值与第二个数组的每个值的差。 这是类似的事情,因为我们可以将两个数字相加,即a + b = c,现在如果只有b和c,则使用cb可以找出'a'。 同样的事情是,在这里我们得到了结果值,我们可以找出完成该对所需的值。 这就是为什么我们要寻找sum2与array1中arrayXNUMX的每个值之差的原因。 如果我们发现这些对只是打印出该对与当前数组元素之间的差异,则这将是必需的对。

给定两个未排序的数组,找到总和为x的所有对

代码

C ++代码在两个未排序的数组中查找具有sum = x的所有对

#include<iostream>
#include<unordered_set>

using namespace std;

void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
{
    unordered_set<int> MAP;
    for (int i = 0; i < l1; i++)
        MAP.insert(arr1[i]);

    for (int j = 0; j < l2; j++)
        if (MAP.find(sum - arr2[j]) != MAP.end())
            cout << sum - arr2[j] << " "<< arr2[j] << endl;
}
int main()
{
    int arr1[] = { 3,6,1,4,8,2};
    int arr2[] = { 2,1,5,7,2,4};
    int sum = 9;
    int l1 = sizeof(arr1) / sizeof(int);
    int l2 = sizeof(arr2) / sizeof(int);
    getPairsofSum(arr1, arr2, l1, l2, sum);
    return 0;
}
8 1
4 5
2 7

 

Java代码在两个未排序的数组中查找具有sum = x的所有对

import java.util.HashMap;

class PairofSumUnsortedArray
{
    public static void getPairsofSum(int arr1[], int arr2[], int l1, int l2, int sum)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        for (int i = 0; i < l1; i++)
            MAP.put(arr1[i], 0);

        for (int j = 0; j < l2; j++)
            if (MAP.containsKey(sum - arr2[j]))
                System.out.println(sum - arr2[j] + " " + arr2[j]);
    }
    public static void main(String[] args)
    {
        int arr1[] = { 3,6,1,4,8,2};
        int arr2[] = { 2,1,5,7,2,4};
        int sum = 9;
        getPairsofSum(arr1, arr2, arr1.length, arr2.length, sum);
    }
}
8 1
4 5
2 7

 

复杂度分析

时间复杂度

O(最大(n,m)) 哪里 “ n”“m”个 是第一和第二个数组的长度。

空间复杂度

O(最大(n,m)) 哪里 “ n”“m”个 是第一和第二个数组的长度。