如何在统计两列表重复元素时实现短路？快速检测A元素在B中的重复情况

嘿，我完全get到你的需求——想要高效地统计列表A中那些在列表B里重复出现的元素数量，同时还要一个布尔版的判断（只要存在这类元素就返回true），而且还得避开拖慢性能的嵌套循环对吧？

其实核心思路很简单：先提前统计列表B中所有元素的出现频次，再用这个频次映射去匹配列表A的元素，这样整体时间复杂度是O(n+m)（n是A的长度，m是B的长度），比嵌套循环的O(n*m)高效太多，尤其是当列表规模较大时。

1. 统计符合条件的元素个数 #

先把列表B转换成元素频次的映射，然后遍历去重后的列表A（避免A里的重复元素重复计数），筛选出在B中出现次数≥2的元素，最后统计数量：

import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class ElementChecker {
    public static long countDuplicateElementsInB(List<String> listA, List<String> listB) {
        // 第一步：统计列表B中每个元素的出现次数
        Map<String, Long> elementFrequencyInB = listB.stream()
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        
        // 第二步：遍历去重后的A，统计在B中出现≥2次的元素数量
        return listA.stream()
                .distinct() // 去重A中的重复元素，避免重复统计
                .filter(element -> elementFrequencyInB.getOrDefault(element, 0L) >= 2)
                .count();
    }
}

对应你的例子：listA = ["A", "B", "C"]，listB = ["X", "B", "B", "A", "C", "C", "C"]，最终返回的结果就是2（B和C在B中都出现了多次）。

2. 布尔判断：是否存在符合条件的元素 #

如果只需要判断A中是否有元素在B里重复出现，不用统计数量，可以用anyMatch提前终止遍历，效率更高：

public static boolean hasElementDuplicatedInB(List<String> listA, List<String> listB) {
    Map<String, Long> elementFrequencyInB = listB.stream()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    
    return listA.stream()
            .distinct()
            .anyMatch(element -> elementFrequencyInB.getOrDefault(element, 0L) >= 2);
}

这个方法一旦找到第一个符合条件的元素就会停止遍历，不需要处理完整个列表A。

3. 不用Streams的写法（更底层一点） #

如果你觉得Streams的可读性或者性能不符合预期，也可以用普通的HashMap和循环实现，逻辑是一样的：

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ElementChecker {
    public static long countDuplicateElementsInB(List<String> listA, List<String> listB) {
        Map<String, Integer> freqMap = new HashMap<>();
        // 统计B的元素频次
        for (String elem : listB) {
            freqMap.put(elem, freqMap.getOrDefault(elem, 0) + 1);
        }
        
        // 去重A
        Set<String> uniqueElementsInA = new HashSet<>(listA);
        
        int count = 0;
        for (String elem : uniqueElementsInA) {
            if (freqMap.getOrDefault(elem, 0) >= 2) {
                count++;
            }
        }
        return count;
    }
    
    public static boolean hasElementDuplicatedInB(List<String> listA, List<String> listB) {
        Map<String, Integer> freqMap = new HashMap<>();
        for (String elem : listB) {
            freqMap.put(elem, freqMap.getOrDefault(elem, 0) + 1);
        }
        
        Set<String> uniqueElementsInA = new HashSet<>(listA);
        for (String elem : uniqueElementsInA) {
            if (freqMap.getOrDefault(elem, 0) >= 2) {
                return true; // 找到就直接返回，不用继续遍历
            }
        }
        return false;
    }
}

不管用哪种写法，核心都是先构建频次映射，再做匹配，这样就能完美避开嵌套循环，同时保证高效性。

内容的提问来源于stack exchange，提问作者Lucas