leetcode中如何解决找不同问题

# LeetCode中如何解决找不同问题

## 引言

在LeetCode的算法题库中，"找不同"（Find the Difference）是一类经典的字符串/数组处理问题。这类问题通常要求在两个相似但有细微差别的数据结构中找出那个唯一的不同元素。本文将系统性地讲解这类问题的常见变体、解决思路、代码实现以及优化技巧。

---

## 问题分类与典型例题

### 1. 基础找不同（389. Find the Difference）
**题目描述**：  
给定两个字符串 `s` 和 `t`，其中 `t` 是由 `s` 随机重排并在随机位置添加一个字母得到的。找出被添加的字母。

**示例**：
```python
输入：s = "abcd", t = "abcde"
输出：'e'

2. 进阶变体（136. Single Number）

题目描述：
非空整数数组中，除某个元素只出现一次外，其余每个元素均出现两次。找出那个只出现一次的元素。

示例：

输入：[4,1,2,1,2]
输出：4

核心解决思路

方法一：哈希表计数

适用场景：通用性强，适合所有找不同变体
时间复杂度：O(n)
空间复杂度：O(n)

步骤： 1. 遍历第一个字符串/数组，统计每个字符/数字的出现次数 2. 遍历第二个字符串/数组，递减计数 3. 当某个字符/数字的计数为负或不存在时，即为目标

代码实现（389题）：

def findTheDifference(s: str, t: str) -> str:
    from collections import defaultdict
    count = defaultdict(int)
    for ch in s:
        count[ch] += 1
    for ch in t:
        count[ch] -= 1
        if count[ch] < 0:
            return ch

方法二：ASCII码求和

适用场景：仅适用于单个字符差异的情况
时间复杂度：O(n)
空间复杂度：O(1)

原理：
利用被添加字符的ASCII码值等于两个字符串ASCII总和之差

代码实现：

def findTheDifference(s: str, t: str) -> str:
    sum_s = sum(ord(ch) for ch in s)
    sum_t = sum(ord(ch) for ch in t)
    return chr(sum_t - sum_s)

方法三：位运算（XOR）

适用场景：存在成对元素和单个不同元素时（如136题）
时间复杂度：O(n)
空间复杂度：O(1)

原理：
- 任何数与0异或等于自身 - 相同数异或等于0 - 异或满足交换律和结合律

代码实现（136题）：

def singleNumber(nums: List[int]) -> int:
    res = 0
    for num in nums:
        res ^= num
    return res

变体问题解决方案

变体1：多个不同元素

例题：给定两个数组，找出所有不同的元素（类似260. Single Number III）

解决方案： 1. 使用哈希表记录出现次数 2. 分组异或法（当需要找出两个不同数字时）

分组异或示例：

def singleNumber(nums: List[int]) -> List[int]:
    xor = 0
    for num in nums:
        xor ^= num
    mask = xor & -xor  # 获取最低位的1
    a, b = 0, 0
    for num in nums:
        if num & mask:
            a ^= num
        else:
            b ^= num
    return [a, b]

变体2：有序数组找不同

例题：两个已排序数组，找出不同的元素（类似二分查找场景）

解决方案： - 双指针法，时间复杂度可优化至O(log n)

复杂度对比

实战技巧

1. 输入验证：始终先检查输入是否为空或长度差是否为1

   if len(t) != len(s) + 1:
      return ''
   

2. 扩展思考：

   • 如果允许修改原数组，可以通过排序后比较（时间复杂度O(n log n)）
   • 对于Unicode字符，哈希表法比ASCII求和更可靠

3. 边界案例：

   • s为空字符串时，t的第一个字符即为答案
   • 包含重复字符的情况（如s=“aabb”, t=“aabcb”）

总结

找不同问题的核心在于发现数据之间的差异特征。通过本文介绍的四种主要方法： 1. 哈希表法——通用性强 2. ASCII求和——针对字符差异 3. 位运算——高效解决数字成对问题 4. 双指针——适用于有序结构

掌握这些方法后，可以解决LeetCode中90%以上的找不同类问题。建议读者在理解原理后，针对389、136、260等题目进行专项练习。

扩展练习

1. 389. Find the Difference
2. 136. Single Number
3. 260. Single Number III
4. 1222. Find the Difference of Two Arrays

”`