DSA问题：去除嵌套数组中元素集合相同的重复子数组及最优复杂度

本问题的核心判定规则为：子数组重复不考虑内部元素的排列顺序，只要两个子数组包含的元素集合（含元素出现次数）完全一致，就判定为重复项，需要保留第一次出现的子数组，移除后续的重复项。

给定输入示例：

let arr = [ [1,2,3] ,[5,6,9] ,[2,1,3],[3,2,4],[4,3,5], [6,9,5] ]

其中：

• arr[0] = [1,2,3] 与 arr[2] = [2,1,3] 元素构成完全一致，仅排列不同，属于重复项
• arr[1] = [5,6,9] 与 arr[5] = [6,9,5] 元素构成完全一致，仅排列不同，属于重复项

期望输出结果：

final = [ [1,2,3] ,[5,6,9] ,[3,2,4],[4,3,5] ]

多语言实现方案 #

JavaScript 实现 #

核心思路：对每个子数组排序消除排列差异，生成可哈希的字符串键，用Set记录已出现的键，仅保留首次出现键对应的原始子数组。

function removeDuplicateSubarrays(arr) {
  const seenKeys = new Set();
  const result = [];
  for (const subArray of arr) {
    // 不修改原始子数组，拷贝后排序生成唯一键
    const uniqueKey = [...subArray].sort((a, b) => a - b).join(',');
    if (!seenKeys.has(uniqueKey)) {
      seenKeys.add(uniqueKey);
      result.push(subArray);
    }
  }
  return result;
}

// 验证测试
const input = [ [1,2,3] ,[5,6,9] ,[2,1,3],[3,2,4],[4,3,5], [6,9,5] ];
// 输出结果与预期完全匹配

Python 实现 #

核心思路与JS一致，利用Python中tuple的可哈希特性，将排序后的子数组转成tuple作为集合去重的键。

def remove_duplicate_subarrays(arr):
    seen_keys = set()
    result = []
    for sub_array in arr:
        unique_key = tuple(sorted(sub_array))
        if unique_key not in seen_keys:
            seen_keys.add(unique_key)
            result.append(sub_array)
    return result

# 验证测试
input_arr = [[1,2,3], [5,6,9], [2,1,3], [3,2,4], [4,3,5], [6,9,5]]
# 输出结果与预期完全匹配

C++ 实现 #

利用C++ STL中set对vector<int>的原生比较支持，将排序后的子数组作为键存储，完成去重。

#include <vector>
#include <set>
#include <algorithm>

std::vector<std::vector<int>> removeDuplicateSubarrays(std::vector<std::vector<int>>& arr) {
    std::set<std::vector<int>> seen;
    std::vector<std::vector<int>> result;
    for (auto& subArray : arr) {
        std::vector<int> key = subArray;
        std::sort(key.begin(), key.end());
        if (!seen.count(key)) {
            seen.insert(key);
            result.push_back(subArray);
        }
    }
    return result;
}

最优时间复杂度分析 #

首先定义变量：设外层数组共包含n个子数组，每个子数组的平均长度为k。
该问题的理论时间下界为Ω(nk)——因为必须遍历完所有数组的全部nk个元素，才能完成重复判定，不存在低于这个量级的算法。

• 基于排序生成键的通用实现：每个子数组的排序操作耗时为O(k log k)，配合哈希查找/插入操作的平均O(k)耗时，整体时间复杂度为O(n*k log k)。这种实现不依赖数值范围，鲁棒性强，是工程场景下的首选方案。
• 理论最优平均复杂度方案：针对每个子数组统计元素出现频次生成哈希键，无需排序，单个数组的处理耗时为O(k)，整体平均时间复杂度为O(n*k)，刚好匹配问题的时间下界。但这种方案的问题是如果数值取值范围极大，哈希键的存储、计算的常数开销会远高于排序方案，且存在哈希碰撞的风险，通用场景下落地成本较高。

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