题目描述

题目1（3. 无重复字符的最长子串）

题目2（567 字符串的排列）

解题思路

题目1（3. 无重复字符的最长子串）

• 使用一个哈希表map存储无重复字符的字串（key），以及在字符串中的位置（value）
• 使用两个指针（start，end）分别指向无重复字符字串的首尾
• 遍历字符串的每个字符，如果map中不存在该字符，将其加入map，并更新当前最大无重复字串长度；若存在，更新start位置。

题目2（567 字符串的排列）

遍历 s2 中的每个长度为 s1.length() 的子串，判断子串和 s1​ 中每个字符的出现次数是否相等，若相等，返回true。

代码实现

题目1（3. 无重复字符的最长子串）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0, start = 0;
        for(int end=0;end<n;end++){
            char temp = s.charAt(end);    //当前字符
            if(map.containsKey(temp)){
                start = Math.max(map.get(temp)+1, start);
            }
            maxLength = Math.max(maxLength, end - start + 1);
            map.put(temp, end);
        }
        return maxLength;
    }
}

题目2（567 字符串的排列）

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;    //s1长度必定不大于s2
        int[] count1 = new int[26];
        int[] count2 = new int[26];

        for(int i=0;i<s1.length();i++){
            ++count1[s1.charAt(i) - 'a'];
            ++count2[s2.charAt(i) - 'a'];
        }
        if(Arrays.equals(count1, count2)) return true;

        for(int i=s1.length();i<s2.length();i++){
            ++count2[s2.charAt(i) - 'a'];
            --count2[s2.charAt(i-s1.length()) - 'a'];
            if(Arrays.equals(count1, count2)) return true;
        }
        return false;
    }
}