滑动窗口
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：暴力枚举法，使用双层for循环，第一层循环为字串的首字符，第二层循环以首字符为基准查找字串的的长度，最后得到最长的字串长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] array = s.toCharArray();
int count = 0;
int maxCount = 0;
for(int i=0 ;i < array.length;i++){
count = 0;
HashSet set = new HashSet();
for(int j = i;j<array.length;j++){
if(set.contains(array[j])) break;
count++;
set.add(array[j]);
}
maxCount = Math.max(count,maxCount);
}
return maxCount;
}
}
使用滑动窗口可以减少一层for循环,使用begin指针标记序列的首字符，遇到重复字符，删除哈希表中begin所指向的元素，同时begin向后移动。
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] array = s.toCharArray();
int count = 0;
int maxCount = 0;
HashSet set = new HashSet();
int begin = 0;
for(int i=0 ;i < array.length;i++){
while(set.contains(array[i])){
maxCount = Math.max(maxCount,count);
set.remove(array[begin]);
begin++;
count--;
}
set.add(array[i]);
count++;
}
return Math.max(maxCount,count);
}
}
找出字符串中的所有字母异位词
给定两个字符串 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" 的异位词。
思路：暴力枚举，将p排序，再遍历s，每次截取与p相同长度的字符串，再排序，与排序后的p比较，相同则保存下标到list
class Solution {
public List<Integer> findAnagrams(String s, String p) {
ArrayList<Integer> list = new ArrayList<>();
char[] p_array = p.toCharArray();
Arrays.sort(p_array);
String key = new String(p_array);
for (int i = 0; i <s.length()-p.length()+1; i++) {
String substring = s.substring(i, i + p.length());
char[] charArray = substring.toCharArray();
Arrays.sort(charArray);
substring = new String(charArray);
if(substring.equals(key))
list.add(i);
}
return list;
}
}