找到四个总和为给定值的元素(哈希图)


难度级别
经常问 亚马逊 谷歌 微软
排列 哈希 排序

问题“查找总和为给定值的四个元素(Hashmap)”指出,假设您有一个整数数组和一个称为sum的数字。 问题语句要求确定数组中是否存在四个元素,这些元素的总和等于给定值“ sum”。 如果为true,则函数输出为“是”,否则输出为“否”。

使用案列

找到四个总和为给定值的元素(哈希图)

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

算法

  1. 遍历循环, 当我<n – 1.
    1. 遍历循环, 而j = i + 1 <n
      1. 将arr [i] + arr [j]的值存储到val中,并检查哈希表中是否存在sum-val。
        1. 如果为true,则获取密钥并找出数字,然后返回true。
      2. 否则,将i和j以及关键字arr [i] + arr [j]放在哈希表中。
  2. 返回false。

说明

我们得到了一个问题语句,该语句要求确定数组中是否存在四个将给定值相加的元素。 如果是,则遵循该功能,然后应打印“是”,否则应打印“否”。 我们将使用 散列 解决这个问题。 因此,我们可以将键存储为元素,将其配对为可能的子数组,将值存储为该索引的索引,以便我们对其进行检查。

让我们考虑一个例子:

使用案列

arr [] = {2,7,3,2,9,5,9,3,25},sum = XNUMX

这里我们举一个例子。 我们已经宣布了 布尔 该函数将返回true和false。 我们还将在地图中使用要使用的对象的对象属性,因为我们的参数之一是任何列表或向量。 因此,基本上,我们将遍历数组,但一次在外部循环中获取数组的每个元素,并在第二个内部循环中遍历前一个索引的其余元素。

我们取两个元素的总和为arr [i] + arr [j],并将其存储到名为val的变量中,然后检查sum-val是否存在于变量中。 哈希表 是否存在,如果不存在,则简单地将元素推入映射,假设我们有数组的元素2和7(arr [i]和arr [j])得到sum为9,而25-9的sum-val为18是哈希表中不存在,因此我们简单地推送9以及当前索引0和1,以便稍后我们可以发现表中是否存在sum-arr [i] + arr [j]。 如果存在,则只需获取键的值并检查键上的某些条件,如果满足,则返回true。 这意味着我们找到了答案。

C ++代码查找四个元素的总和为给定值(哈希图)

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}
Yes

Java代码查找四个元素的总和为给定值(哈希图)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}
Yes

复杂度分析

时间复杂度

2哪里 “ n” 是数组中元素的数量。 使用HashMap可以使我们实现这个时间的复杂性,否则是不可能的。

空间复杂度

2哪里 “ n” 是数组中元素的数量。 在最坏的情况下,可能需要将N ^ 2对存储在地图中。 因此,空间复杂度是多项式。