• leetcodehot 100 ----滑动窗口


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

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

    示例 1:
    
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
    示例 2:
    
    输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
    示例 3:
    
    输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
         请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    提示:

    0 <= s.length <= 5 * 104
    s 由英文字母、数字、符号和空格组成

    class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int maxLength = 0;
        int start = 0, end = 0;
        
        while (start < n && end < n) {
            char c = s.charAt(end);
            if (!set.contains(c)) {
                set.add(c);
                maxLength = Math.max(maxLength, end - start + 1);
                end++;
            } else {
                set.remove(s.charAt(start));
                start++;
            }
        }
        
        return maxLength;
    }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    思路:hashset+快慢指针(滑动窗口)

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

    给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

    异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

    示例 1:
    
    输入: s = "cbaebabacd", p = "abc"
    输出: [0,6]
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
     示例 2:
    
    输入: s = "abab", p = "ab"
    输出: [0,1,2]
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    提示:

    1 <= s.length, p.length <= 3 * 104
    s 和 p 仅包含小写字母

    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int sLen = s.length(), pLen = p.length();
    
            if (sLen < pLen) {
                return new ArrayList<Integer>();
            }
    
            List<Integer> ans = new ArrayList<Integer>();
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            for (int i = 0; i < pLen; ++i) {
                sCount[s.charAt(i) - 'a']++;
                pCount[p.charAt(i) - 'a']++;
            }
    
            if (Arrays.equals(sCount, pCount)) {
                ans.add(0);
            }
    
            for (int i = 0; i < sLen - pLen; ++i) {
                sCount[s.charAt(i) - 'a']--;
                sCount[s.charAt(i + pLen) - 'a']++;
    
                if (Arrays.equals(sCount, pCount)) {
                    ans.add(i + 1);
                }
            }
    
            return ans;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
  • 相关阅读:
    定时任务(一)
    Google Authenticator 算法
    【问题思考总结】为什么一点的泰勒展开可以在任意点逼近函数?【泰勒公式 泰勒定理的适用范围】
    JAVA毕业设计高校勤工助学管理系统计算机源码+lw文档+系统+调试部署+数据库
    Java OA系统任务协作模块
    Nginx高可用 - Keepalived安装部署
    C++ Decltype 关键字
    Android Canvas的使用
    python安装第三方包
    机器人xacro设计+gazebo/rviz启动
  • 原文地址:https://blog.csdn.net/qq_57818853/article/details/133266476