1. 概述
在本教程中，我们将讨论如何从一个包含 2N 只袜子的数组中高效地配对出 N 对袜子。
首先我们会明确问题，并通过一个例子进行说明。接着会介绍一个朴素解法，然后提出两种优化方案，分别是排序法和哈希法。
2. 问题定义
假设我们有一个长度为 2N 的数组，其中包含 N 对袜子。每只袜子可能有多个属性，如颜色、尺码等。我们的任务是将这些袜子按照属性配对。
举个例子来帮助理解：
我们有一个包含 8 只袜子的数组，每只袜子都有颜色和尺码属性：
图中每个格子的颜色代表袜子的颜色，数字代表尺码。我们需要将相同颜色和尺码的袜子配对：
本教程仅讨论找到一种可行的配对方式，不考虑存在多个解的情况。
3. 朴素解法
3.1. 核心思路
遍历数组，对每只未配对的袜子，再次遍历数组寻找匹配项。
3.2. 实现代码
algorithm findSimilarPairsNaive(N, sock):
// INPUT
// N = the number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
taken <- an array of false, with length 2 * N
for i <- 0 to 2 * N - 1:
if taken[i] is true:
continue
taken[i] <- true
for j <- i + 1 to 2 * N - 1:
if sock[i] = sock[j]:
answer <- add (sock[i], sock[j]) to answer
taken[j] <- true
break
return answer
我们维护一个 taken 数组来记录每只袜子是否已被配对。外层循环遍历每个元素，内层循环查找匹配项。
3.3. 时间复杂度分析
时间复杂度为 **O(N²)**。
外层循环遍历 2N 个元素，内层循环平均查找 N 次。总操作数约为 N * N = N²。
4. 排序法
4.1. 核心思路
先对袜子数组进行排序。这样相同属性的袜子就会相邻，只需一次遍历即可完成配对。
4.2. 实现代码
algorithm findSimilarPairsSorting(N, sock):
// INPUT
// N = the number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
sorted <- sort(sock)
i <- 0
while i <= 2 * N - 2:
if sorted[i] = sorted[i + 1]:
answer <- add (sorted[i], sorted[i + 1]) to answer
i <- i + 1
i <- i + 1
return answer
先对数组排序，然后依次检查相邻元素是否相同。
4.3. 时间复杂度分析
时间复杂度为 **O(N log N)**。
排序时间复杂度是 O(N log N)，遍历为 O(N)，因此整体复杂度由排序决定。
5. 哈希法
5.1. 核心思路
使用 HashSet 记录已经遍历过的袜子。当遇到相同属性的袜子时，配对并移除。
5.2. 实现代码
algorithm findSimilarPairsHash(N, sock):
// INPUT
// N = the Number of pairs of socks
// sock = the array that represents the socks
// OUTPUT
// Returns similar pairs of socks in sock
answer <- an empty sequence
hash_set <- create an empty hash set
i <- 0
while i < 2 * N:
if hash_set contains sock[i]:
answer <- add (sock[i], hash_set.get(sock[i])) to answer
hash_set.delete(sock[i])
else:
hash_set.add(sock[i])
i <- i + 1
return answer
使用 HashSet 存储已遇到的袜子。如果当前袜子已经在集合中，则配对成功并移除；否则加入集合。
5.3. 时间复杂度分析
时间复杂度为 **O(N)**。
我们遍历数组一次，每次操作（查找、添加、删除）的时间复杂度都是 O(1)。
6. 总结
本文讨论了三种解决袜子配对问题的方法：
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
| ✅ 朴素法 | O(N²) | 简单直观但效率低，适合小数据集 |
| ✅ 排序法 | O(N log N) | 性能较好，适合中等规模数据 |
| ✅ 哈希法 | O(N) | 性能最佳，推荐使用 |
如果你追求效率，哈希法是首选方案。它在时间复杂度上最优，实现也相对简单。