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

LeetCode【438】找到字符串中所有字母异位词

news 2025/7/9 19:45:20

题目：
在这里插入图片描述

注意：下面代码勉强通过，每次都对窗口内字符排序。然后比较字符串。

代码：

public List<Integer> findAnagrams(String s, String p) {int start = 0, end = p.length() - 1;List<Integer> result = new ArrayList<>();char[] subArr = p.toCharArray();Arrays.sort(subArr);String subStr = new String(subArr);while (end < s.length()) {char[] charArr = s.substring(start, start + p.length()).toCharArray();Arrays.sort(charArr);String fatherStr = new String(charArr);if (fatherStr.equals(subStr)) {result.add(start);}start++;end++;}return result;}

优化思路：
用数组表示字符出现的次数，最后比较两个数组是否相等即可。

 public static List<Integer> findAnagrams(String s, String p) {int[] sArr = new int[26];int[] pArr = new int[26];List<Integer> result = new ArrayList<>();if (s.length() < p.length()) {    // 注意子串比父串长的情况return result;}// 初始化for (int i = 0; i < p.length(); i++) {sArr[s.charAt(i) - 'a']++;pArr[p.charAt(i) - 'a']++;}if (Arrays.equals(sArr, pArr)) {result.add(0);}for (int i = 0; i < s.length() - p.length(); i++) {sArr[s.charAt(i + p.length()) - 'a']++;sArr[s.charAt(i) - 'a']--;if (Arrays.equals(sArr, pArr)) {result.add(i + 1);    // 注意，这里是 i+1 不是i}}return result;
}