欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

算法 014：查找字符串中的所有字母反义词

最编程 2024-07-17 18:29:06
...

找到字符串中所有字母异位词. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/find-all-anagrams-in-a-string/

什么叫异位词？根据题目的说法，abc和cab就是一组异位词

示例一：cbaebabacd和abc，异位词就是第0下标的cba，和第6下标的bac

题目的要求就是返回这些异位词的起始索引，也就是下标。

 对于这个题目来说，我们可以使用滑动窗口，不过这个题目的滑动窗口和之前的题目不太一样       ，之前的题目是滑动窗口的大小是根据right和left指针的位置而变化的，这个题目的滑动窗口是固定死的，长度为3。

我们只需要用hash表来判断，滑动窗口里面的三个数，和要求的三个数，hash值是不是一样。

如果一样，就说明这是异位词，添加到返回的数组中去。

当左边和右边的abc的hash值相等的时候，就代表着此时找到的数组就是我们需要的。

但是因为滑动窗口的大小不好保持在3，我们使用一个变量count来统计窗口中有效字符的个数；

当左边的hash从0变成1，count++；反之则count--。要注意的是我们给count加减的判断条件是，左边的hash值小于等于右边的hash值才count++，count--也是同样的道理。

代码：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        
        int[] hash2 = new int[26];
        for(char ch : pp){
            hash2[ch - 'a']++;
        }
        int[] hash1 = new int[26];
        int m = pp.length;
        for(int left = 0, right = 0, count = 0; right < ss.length; right++){
            char in = ss[right];
            hash1[in - 'a']++;
            if(hash1[in - 'a'] <= hash2[in - 'a']){
                count++;
            }
            if(right - left + 1 > m){
                char out = ss[left++];
                if(hash1[out - 'a'] <= hash2[out - 'a']){
                    count--;
                }
                hash1[out - 'a']--;
            }
            if(count == m){
                ret.add(left);
            }
        }
        return ret;
    }
}

上一篇： Javascript 构造函数和类

下一篇： js 函数属性和方法

推荐阅读