滑动窗口问题

leetcode 3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1: 输入: "abcabcbb"  输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:  输入: "bbbbb"  输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:  输入: "pwwkew"  输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

维持一个左子针left和一个右子针right。right-left就是无重复子串的长度。遍历规律为，

没有重复的话，right向右移动一位。

有重复的话，left右移并更新最长字符串max的值，右移一直到滑动窗口内无重复字符。即tmp[s.charAt(r)] == 0

public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        int[] tmp = new int[256];
        int maxlen = 0;
        int l = 0;
        int r = 0;

        while (l<s.length()){
            if(r<s.length() && tmp[s.charAt(r)] == 0){
                tmp[s.charAt(r++)] = 1;
            }else {
                maxlen = maxlen > (r-l)?maxlen : (r-l);
                tmp[s.charAt(l++)] = 0;
            }
        }

        return maxlen;
    }

--------------------------

leetcode 438. 找到字符串中所有字母异位词

public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0 || s.length() < p.length()) {
            return list;
        }
        int len = p.length();
        int[] tmp = new int[26];
        int[] windonw = new int[26];

        for (int i = 0; i < len; i++) {
            tmp[p.charAt(i) - 'a']++;        // 记录p串有哪些字符
            windonw[s.charAt(i) - 'a']++;
        }
        int l = 0;
        int r = len;
        while (r < s.length()) {
            if (cmp(windonw, tmp)) {
                list.add(l);
            }
            windonw[s.charAt(r++) - 'a']++;
            windonw[s.charAt(l++) - 'a']--;

        }
        if (cmp(windonw, tmp)) {    //末尾的那个
            list.add(l);
        }
        return list;

    }

    private boolean cmp(int[] array1, int[] array2) {
        for (int i = 0; i < array1.length; i++) {
            if (array1[i] != array2[i]) {
                return false;
            }

        }
        return true;
    }