• 无重复字符的最长子串
• 找到字符串中所有字母异位词

---

无重复字符的最长子串

滑动窗口，[b, i] 为不重复子串。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] cs = s.toCharArray();
        int max = 0;
        // [b, i] 即为不重复子串
        int b = 0;      // 滑动窗口左边界，不重复子串的索引起始处
        HashMap<Character, Integer> map = new HashMap<>();   // 存字符的最新位置。
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            // 如果没存，那存。如果存了，就更新b的位置
            // 注意更新是：大了才更新，因为可能当前字符是老字符，已经被包含了。
            // "abba"，到第二个b时，b是1 + 1 = 2；到第二个a时，0+1=1，不该更新。
            Integer pos = map.get(c);
            if (pos != null) {
                b = Math.max(pos + 1, b);
            }
            map.put(c, i);
            max = Math.max(max, i - b + 1);
        }
        return max;
    }
}

将HashMap换成手动字典，没什么大用

// 3. 无重复字符的最长子串
// 2ms
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] cs = s.toCharArray();
        int max = 0;
        int b = 0;      // 滑动窗口左边界
        int[] map = new int[200];    // HashSet
        Arrays.fill(map, -1);   
        for (int i = 0; i < cs.length; i++) {
            char c = cs[i];
            int c_index = c;
            if (map[c_index] != -1) {
                b = Math.max(map[c_index] + 1, b);
            }
            map[c_index] = i;
            max = Math.max(max, i - b + 1);
        }
        return max;
    }
}

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

全是小写字母，那就搞new int[26]，记录个数。

滑动窗口，比较数组Arrays.equals()

// 438. 找到字符串中所有字母异位词
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if(p.length() > s.length()){
            return result;
        }

        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        int[] ip = new int[26];
        int[] is = new int[26];
        
        for (int i = 0; i < cp.length; i++) {
            char c = cp[i];
            ip[c - 'a']++;
            c = cs[i];
            is[c - 'a']++;
        }

        if (Arrays.equals(ip, is)) {
            result.add(0);
        }

        for (int i = cp.length; i < cs.length; i++) {
            char c = cs[i - cp.length];
            is[c - 'a']--;

            c = cs[i];
            is[c - 'a']++;

            if (Arrays.equals(ip, is)) {
                result.add(i - cp.length + 1);
            }
        }
        return result;
    }
}