网络空间安全专业_服务器租用1元_自助建站免费搭建个人网站_网络公关公司

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

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

思路：双指针指向不含重复字符的连续字串的头和尾，用集合存储子串中的元素，有重复时，左指针持续右移，无重复后统计长度

class Solution {public int lengthOfLongestSubstring(String s) {int i = 0; // 左边界int j = 0; // 右边界int n = s.length();int len = 0; // 记录最长不重复子串的长度if(n == 0){return 0;}// 使用 HashSet 来存储当前窗口内的字符，用于快速判断字符是否重复Set<Character> set = new HashSet<>();
​while(j < n){// 如果当前字符已经在窗口内，说明出现了重复字符// 需要移动左边界 i，直到窗口内没有重复字符为止while(set.contains(s.charAt(j))){set.remove(s.charAt(i));++i;}
​len = Math.max(j - i, len);set.add(s.charAt(j));++j;}// 因为在循环中计算长度时没有加 1，所以这里需要加 1return len + 1;}
}

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

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

思路：维护一个固定长度的窗口，向后遍历，每前进一步就检查当前窗口是否满足条件，满足条件就记录下来

class Solution {public List<Integer> findAnagrams(String s, String p) {// 获取字符串 s 和 p 的长度int sLen = s.length(), pLen = p.length();
​// 如果 s 的长度小于 p 的长度，直接返回空列表// 因为 s 中不可能包含 p 的字母异位词if (sLen < pLen) {return new ArrayList<Integer>();}
​// 初始化结果列表，用于存储所有字母异位词的起始索引List<Integer> ans = new ArrayList<Integer>();
​// 初始化两个数组，分别用于统计 s 和 p 中字符的频率int[] sCount = new int[26]; // 统计 s 中字符的频率int[] pCount = new int[26]; // 统计 p 中字符的频率
​// 初始化窗口，统计 s 的前 pLen 个字符和 p 中所有字符的频率for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a']; // 统计 s 的前 pLen 个字符++pCount[p.charAt(i) - 'a']; // 统计 p 中的所有字符}
​// 检查初始窗口是否是 p 的字母异位词// 如果两个频率数组相等，则说明 s 的前 pLen 个字符是 p 的字母异位词if (Arrays.equals(sCount, pCount)) {ans.add(0); // 将起始索引 0 添加到结果列表中}
​// 使用滑动窗口遍历 s，窗口大小固定为 pLenfor (int i = 0; i < sLen - pLen; ++i) {// 更新窗口：// 1. 移除窗口左边界字符的计数--sCount[s.charAt(i) - 'a'];// 2. 添加窗口右边界字符的计数++sCount[s.charAt(i + pLen) - 'a'];
​// 检查当前窗口是否是 p 的字母异位词if (Arrays.equals(sCount, pCount)) {ans.add(i + 1); // 如果是，将当前窗口的起始索引添加到结果列表中}}
​// 返回结果列表return ans;}
}