高效实现双数组公共项移除、求和匹配剔除的最优逻辑方案

高效实现思路与代码 #

针对你提出的数组处理需求，我们可以分三个阶段优化操作，尽可能降低时间复杂度：

1. 快速移除两个数组的公共元素

首先，我们需要高效找出两个数组的公共元素，这里用**哈希集合（Hash Set）**是最优选择，因为集合的查找操作时间复杂度为O(1)。具体步骤：

• 将arr1和arr2分别转换为集合，得到set1和set2
• 计算两个集合的交集common_elements，这就是所有公共元素的集合
• 从原数组中过滤掉属于common_elements的元素，得到两个仅包含非公共元素的列表non_common_arr1和non_common_arr2

这一步的时间复杂度是O(n + m)，其中n和m分别是arr1和arr2的长度，远优于双重循环比对的O(n*m)。

2. 高效检查元素是否为对方数组两个及以上元素的和

这一步最容易陷入O(k²)的暴力枚举，我们可以通过哈希表（Hash Map）统计元素频率来优化：

• 先为其中一个非公共数组（比如non_common_arr2）构建频率字典count_map2，key是元素值，value是该元素出现的次数
• 遍历non_common_arr1中的每个元素x，检查是否存在至少两个元素（可重复）在non_common_arr2中相加等于x：
  • 遍历count_map2的每个键y，计算补数complement = x - y
  • 如果complement在count_map2中：
    • 若complement == y：需要count_map2[y] >= 2（即至少有两个y可以相加得到x）
    • 若complement != y：只要count_map2[complement] >= 1即可（y和complement各至少有一个，相加得到x）
  • 一旦找到满足条件的组合，标记x需要移除，停止当前元素的检查
• 用同样的方法处理non_common_arr2中的元素，检查是否能由non_common_arr1中两个及以上元素相加得到

这一步的时间复杂度是O(ab + cd)，其中a是non_common_arr1的长度，b是non_common_arr2的不同元素数量；c是non_common_arr2的长度，d是non_common_arr1的不同元素数量，比暴力枚举的O(a² + c²)高效得多，尤其是当数组存在大量重复元素时。

3. 生成最终剩余数组

过滤掉所有满足和条件的元素，得到最终的两个剩余数组。

Python 代码示例 #

from collections import defaultdict

def process_arrays(arr1, arr2):
    # 步骤1：移除公共元素
    set1 = set(arr1)
    set2 = set(arr2)
    common = set1 & set2
    
    non_common_arr1 = [num for num in arr1 if num not in common]
    non_common_arr2 = [num for num in arr2 if num not in common]
    
    # 步骤2：构建频率字典
    def build_count_map(arr):
        count_map = defaultdict(int)
        for num in arr:
            count_map[num] += 1
        return count_map
    
    count_map1 = build_count_map(non_common_arr1)
    count_map2 = build_count_map(non_common_arr2)
    
    # 检查元素是否能由目标数组中两个及以上元素相加得到
    def should_remove(x, target_count_map):
        for y in target_count_map:
            complement = x - y
            if complement in target_count_map:
                if complement == y:
                    if target_count_map[y] >= 2:
                        return True
                else:
                    return True
        return False
    
    remaining_arr1 = [num for num in non_common_arr1 if not should_remove(num, count_map2)]
    remaining_arr2 = [num for num in non_common_arr2 if not should_remove(num, count_map1)]
    
    return remaining_arr1, remaining_arr2

# 测试示例
arr1 = [1, 3, 5, 7, 9, 10]
arr2 = [3, 7, 11, 13, 5, 20]
result1, result2 = process_arrays(arr1, arr2)
print("剩余arr1元素:", result1)
print("剩余arr2元素:", result2)

边界情况说明 #

• 处理负数：哈希表和集合对负数的处理和正数一致，无需额外逻辑
• 重复元素：频率字典会统计元素出现次数，确保“两个及以上元素相加”的条件准确
• 空数组：如果某一步得到空数组，后续检查会直接跳过，返回空数组

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