剑指offer 2 day5

字符串中的变位词

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()){
            return false;
        }
        int[] a = new int[26];
        int[] b = new int[26];
        for(int i = 0;i < s1.length();i++){
            a[s1.charAt(i) - 'a']++;
            b[s2.charAt(i) - 'a']++;
        }
        if(Arrays.equals(a,b)){
            return true;
        } 
        int left = 0,right = s1.length();
        while(right < s2.length()){
            b[s2.charAt(right) - 'a']++;
            b[s2.charAt(left) - 'a']--;
            if(Arrays.equals(a,b)){
                return true;
            }
            right++;
            left++;
        }
        return false;
    }
}

滑动窗口+计数
使用两个数组a和 b，a统计s1中各个字符的个数，b统计当前遍历字串的各个字符的个数。
由于需要遍历的子串长度均为s1的长度，我们可以使用一个固定长度为s1.length的滑动窗口来维护b:滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断a是否与b相等，若相等则意味着s1的变位词之一是s2的子串。
时间复杂度：O(m+n+∣Σ∣)
Σ->小写字母的长度
空间复杂度：O(∣Σ∣)

字符串中的所有变位词

class Solution {
    public List findAnagrams(String s, String p) {
        int sl = s.length(), pl = p.length();
        List list = new ArrayList<>();
        if (pl > sl) {
            return list;
        }
        int[] a = new int[26];
        int[] b = new int[26];
        for (int i = 0; i < pl; i++) {
            a[s.charAt(i) - 'a']++;
            b[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(a, b)) {
            list.add(0);
        }
        int left=0,right=pl;
        while(right 
滑动窗口+计数
 在上题的基础上略作修改即可
 时间复杂度：O(m+n+∣Σ∣)
 空间复杂度：O(∣Σ∣)
 
不含重复字符的最长字符串
 
 
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int[] dic = new int[128];
        for (int r = 0,l = 0;r < s.length();r++) {
            dic[s.charAt(r)]++;
            while (dic[s.charAt(r)] > 1) {
                dic[s.charAt(l++)]--;
            }
            max = Math.max(max,r - l + 1);
        }
        return max;
    }
}
 
滑动窗口
 用字典来记录窗口中已经出现的字符
 如果字符在字典中没有出现，则移动右指针并计数，如果出现了，则移动左指针并更新字典
 时间复杂度：O(n+∣Σ∣)
 空间复杂度：O(1)