java - 如何使用 hashmap 数据类型在满足 ab = cd 且时间复杂度为 O(n²) 的数组中找到所有对 (a,b) 和 (c,d)

Question

给定一个整数列表，如何在最小时间复杂度下找到所有对(即 a x b = c x d；使得 a != b != c != e)？

我试过使用 hashmap 数据类型，它基本上进行乘积计算，检查它是否已经在 hashmap 中找到，如果是，它将嵌套 for 循环的增量计数器的值归因于 Pair 对象在 HashMap 中找到的类型。

Pair 是一个对象，存储一对中第一个和第二个数字的索引。 HashMap 将产品存储为键，将对存储为值。

我的代码的问题是，当涉及到以下场景时......

a x b = c x d = e x f

...它不起作用，因为它只创建以下链接...

a x b = c x d 和 a x b = e x f

...并且无法到达:

c x d = e x f

例如，下面的数组会产生不正确的结果:

int[] A = {1,2,3,4,6,12};

我认为唯一的问题是因为 HashMap 只为给定的键取一个值。我曾尝试将 hashmap 声明更改为成对数组，但很快意识到我需要添加另一个 for 循环，从而增加了时间复杂度。

有什么想法可以保持 O(n²) 并提供正确的结果吗？

Answer 1

我的看法:

为每个产品存储一组对。这应该处理重复项。如果 Pairs 由相同的数字组成，则需要将它们视为相等。

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;

public class Main {

  static int[] data = {1,2,3,4,6,12};

  static class Pair {

    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public int x;
    public int y;

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Pair pair = (Pair) o;
      return
        x == pair.x && y == pair.y ||
        x == pair.y && y == pair.x;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x * y);
    }
  }

  public static void main(String[] args){

    HashMap<Integer, HashSet<Pair>> products = new HashMap<>();

    // index all pairs by product in o^2 loop
    for (int i=0;i<data.length;i++){
      for (int j=i+1;j<data.length;j++){
        int a = data[i];
        int b = data[j];
        Integer p = a*b;
        if (!products.containsKey(p)){
          products.put(p, new HashSet<>());
        }
        HashSet<Pair> knownPairs = products.get(p);
        Pair pair = new Pair(a, b);
        knownPairs.add(pair);
      }
    }

    // output results
    for (Integer product: products.keySet()) {
      System.out.print("product: "+product+" -");
      HashSet<Pair> pairs = products.get(product);
      for (Pair pair : pairs) {
        System.out.print(" "+pair.x+"x"+pair.y);
      }
      System.out.println();
    }


  }

}