当前位置：首页 > ai >正文

LeetCode算法日记 - Day 31: 判定是否互为字符重排、存在重复元素

ai 2025/9/5 11:50:39

1. 判定是否互为字符重排

1.1 题目解析

1.2 解法

1.3 代码实现

2. 存在重复元素

2.1 题目解析

2.2 解法

2.3 代码实现

1. 判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = "abc", s2= "bca"输出: true

示例 2：

输入: s1= "abc", s2= "bad"输出: false

说明：

0 <= len(s1) <= 100
0 <= len(s2) <= 100

1.1 题目解析

题目本质：
这是一个字符串是否为彼此排列（Permutation）的判断问题，本质就是：两个字符串如果能通过字符重新排列互相变成对方，那么它们的字符种类与每个字符的出现次数必须完全一致。

常规解法：
最直观的想法是：直接把两个字符串分别排序，再看排序后的结果是否相等。比如 "abc" → "abc"，"bca" → "abc"，一样就返回 true。

问题分析：
排序的时间复杂度是 O(n log n)，而这里字符串长度最多只有 100，虽说还能接受，但显然有更高效的方法。如果只关心字符频率，那我们没必要做排序，直接统计频次对比即可。

思路转折：
要想更高效 → 必须抛弃排序 → 转而使用一个数组或哈希表统计每个字符的出现次数。
这样我们可以用 O(n) 时间完成频次统计，再用一次 O(26) 的扫描（常数级），就能完成对比。总体复杂度压缩到 O(n)。

1.2 解法

算法思想：
用两个长度为 26 的数组（因为题目保证是小写字母），分别统计 s1 和 s2 的每个字母出现次数；最后逐一对比两个数组，如果完全一致，返回 true，否则返回 false。公式思想就是：

∀ c ∈ [a..z], freq1[c] == freq2[c]

i）长度不相等直接返回 false。

ii）定义两个长度 26 的整型数组 hash1, hash2。

iii）遍历 s1，对每个字符 c，执行 hash1[c-'a']++。

iiii）遍历 s2，对每个字符 c，执行 hash2[c-'a']++。

iiiii）遍历 26 个位置，若出现 hash1[k] != hash2[k]，返回 false。

iiiiii）否则返回 true。

易错点：

忘记提前判断字符串长度是否相等，会导致不必要的统计。
字符数组索引要减 'a'，否则会越界。
比较时要检查所有字符，不能在某个字符相等时就提前返回 true。

1.3 代码实现

class Solution {public boolean CheckPermutation(String ss1, String ss2) {// 长度不等，必然不是排列if (ss1.length() != ss2.length()) return false;int[] hash1 = new int[26];int[] hash2 = new int[26];// 统计 s1 的字符频率for (int i = 0; i < ss1.length(); i++) {hash1[ss1.charAt(i) - 'a']++;}// 统计 s2 的字符频率for (int j = 0; j < ss2.length(); j++) {hash2[ss2.charAt(j) - 'a']++;}// 对比频率表for (int k = 0; k < 26; k++) {if (hash1[k] != hash2[k]) {return false;}}return true;}
}

复杂度分析：

时间复杂度：O(n)，其中 n = 字符串长度。
空间复杂度：O(1)，只用到了固定大小的数组。

2. 存在重复元素

217. 存在重复元素 - 力扣（LeetCode）

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]

输出：true

解释：

元素 1 在下标 0 和 3 出现。

示例 2：

输入：nums = [1,2,3,4]

输出：false

解释：

所有元素都不同。

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

2.1 题目解析

题目本质：
判断数组里是否存在“出现次数≥2”的元素。等价于：在遍历过程中，某个数第二次出现时立即判定为真。

常规解法：
i）朴素双重循环，两两比较找相等，最坏 O(n^2)；
ii）排序后线扫，比较相邻是否相等，O(n log n)。

问题分析：
当 n 可达 1e5 时，O(n^2)会超时；排序法虽可行，但不是最优。更直接的思路是“是否见过”查询，借助哈希集合可将查重降到摊还 O(1)，整体 O(n)。

思路转折：
要想线性时间 → 必须用集合记录已见元素：第一次见到放入集合；若再次见到（add 失败），即可返回 true。若想进一步节省空间且能接受 O(n log n)，可选择排序+线扫。

2.2 解法

算法思想：
维护一个 HashSet。遍历 nums：尝试将当前元素插入集合；若插入失败（说明已存在），立刻返回 true；遍历结束仍未失败，返回 false。

i）新建空集合 seen。

ii）对每个 x：

执行 seen.add(x)；
若返回 false，说明 x 已在集合中，直接返回 true。

iii）遍历结束仍未命中，返回 false。

易错点：

不要用“数值当数组下标”的计数法处理本题（值域含负数且可达 ±1e9，容易越界/占用巨大空间）。
逻辑方向别反：发现重复应返回 true，全部不同才返回 false。
若改用排序法，注意排序会改变原数组顺序；若后续还需原序，先拷贝。

2.3 代码实现

import java.util.HashSet;
import java.util.Set;class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> seen = new HashSet<>();for (int x : nums) {if (!seen.add(x)) { // 已经存在，add 失败return true;    // 有重复}}return false; // 没有重复}
}

复杂度分析：