Java 判断重复的两个二维表算法

我不确定有没有办法将其降低到O(n^2)以下，但要将其降低到O(n^2)，我们可以将List.contains、O(n)乘以HashMap.get，这是O(1)的时间复杂度.

建议不判断contains，而是找到列表a中元素的索引，b个元素将获得该索引并获得相应的a列表.

首先，构建一个包含a个元素作为关键字、值作为其索引的Map.

    Map<String, Set<Integer>> aInSet = new HashMap<>();
    
    for (int i = 0; i < a.size(); i++) {
        for (String elem : a.get(i)) {
            Set<Integer> elementSet = aInSet.getOrDefault(elem, new HashSet<>());
            elementSet.add(i);
            aInSet.put(elem, elementSet);
        }
     }

下面是aInSet的输出，现在我们有了属于的元素的索引列表.

a=[0, 2], b=[0], c=[0], d=[1, 2], e=[1], f=[1, 2]

然后，我们组合b中的元素列表的索引，以获得a中的相应索引.

不算[a, d]英镑，我们有一套加在一起的[0, 1, 2]英镑.以下是代码

    Map<List<String>, List<List<String>>> result = new HashMap<>();

    for (List<String> elem : b) {
        Set<Integer> elemSet = new HashSet<>();
        for (String elemB: elem) {
            elemSet.addAll(aInSet.getOrDefault(elemB, new HashSet<>()));
        }
        List<List<String>> listContainElem = elemSet.stream()
            .map(a::get)
            .collect(Collectors.toList());
        result.put(elem, listContainElem);
    }