14.【滑动窗口】---找到字符串中所有字母异位词

用户11288958

发布于 2025-01-20 17:56:10

6700

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

题目传送门

方法一：滑动窗口

算法原理

新建两个哈希表（数组模拟）：通过比较两个哈希表是否一样用来判断是否是异位词 hashS用来统计字符串s的字符出现次数， hashP用来统计字符串p的字符出现次数，通过滑动窗口每当right - left + 1 > 字符串p的长度的时候。此时令 left++并让left-‘a’指向的字符出现次数-- 来保证这个窗口大小是 <= 字符串p的长度每当窗口大小等于字符串p的长度，就比较两个hash数组是否一样。若一样，就添加left下标到ret顺序表中

class Solution {
    public List<Integer> findAnagrams(String s0, String p0) {
        int[] hashS = new int[26]; //通过比较两个哈希表是否一样用来判断是否是异位词
        int[] hashP = new int[26];
        char[] s = s0.toCharArray();//字符串转数组，方便求解
        char[] p = p0.toCharArray();
        int m = s0.length(),n = p0.length(); //得到两字符串长度
        List<Integer> ret = new ArrayList<>();

        for (int i = 0; i < n; i++) {   //将p字符串扔进拟哈希表p。等待与拟哈希表s进行比较
            hashP[p[i] - 'a']++;
        }
        for (int left = 0,right = 0; right < m; right++) {
            hashS[s[right] - 'a']++;    //进窗口
            if(right - left + 1 > n){   //如果进多了，那么就出窗口。
                hashS[s[left++]-'a']--;
            }
            if (Arrays.equals(hashS, hashP)){ //此时窗口大小一定为p数组长度的大小。
                ret.add(left); //比较两哈希表是否一致，如果一致，就添加初始索引。
            }
        }
        return ret; //最终返回初始索引数组集
    }
}

后面自己写出来的

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashS = new int[26];
        int[] hashP = new int[26];
        List<Integer> ret = new ArrayList<>();
        int m = s.length(),n = p.length();

        for(int i = 0; i < n; i++){
            hashP[p.charAt(i)-'a']++;
        }

        for(int left = 0,right = 0; right < m; right++){
            hashS[s.charAt(right) - 'a']++;
            if(right - left + 1 > n){
                hashS[s.charAt(left++) - 'a']--;
            }
            if(Arrays.equals(hashS,hashP)){
                ret.add(left);
            }
        }
        return ret;
    }
}

再小小优化一下

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashS = new int[26];
        int[] hashP = new int[26];
        List<Integer> ret = new ArrayList<>();
        int m = s.length(),n = p.length();

        for(int i = 0; i < n; i++){
            hashP[p.charAt(i)-'a']++;
        }

        for(int left = 0,right = 0; right < m; right++){
            hashS[s.charAt(right) - 'a']++;
            if(right - left + 1 > n){
                hashS[s.charAt(left++) - 'a']--;
            }if(right - left + 1 == n && Arrays.equals(hashS,hashP)){
                ret.add(left);
            }
        }
        return ret;
    }
}