第一题 无重复字符串的最长子串
思路
其实就是在字符串S中 找到没有重复的最长子串的长度 这道题的难点就是在于如何判断最长并且无重复
首先 最长长度 可以使用变量max记录保存
再者 判断有无重复 最简单的方法就是 暴力遍历法 即对于每次找的子串都再次寻找遍历一次 判断是否已有字符 自然 这种方法判断的话 时间复杂度会不是一般的高
当然 算法优化我们慢慢再讨论 最直接的思路就是如此
解法一：暴力法
我们的暴力当然和上述思路不太一样 我们对于是否重复 可以直接利用Map集合key不能重复的特点 然后使用containKey()方法直接进行判断
class Solution {
public static int lengthOfLongestSubstring(String s) {
// 对于S的特殊情况直接返回0
if(s==null || s.length()==0) return 0;
//将S转化为char数组[] 遍历该数组 然后进行判断
char[] charArray = s.toCharArray();int max=1;
Map<Character,Integer> map=new HashMap<>();
//遍历 每次遍历开始就是认定为子串的起始字符
for(int i=0;i< charArray.length;i++){
//每次记录完一次后 需要把map清空
map.clear();
map.put(charArray[i],i); //将第一个字符放入
for(int j=i+1;j< charArray.length;j++){
if(map.containsKey(charArray[j])){ // 利用containKey方法直接判断
if(map.size()>max) max=map.size(); // 判断当前map长度和max进行比较
break;
}else{
map.put(charArray[j],j);
}
}
if(map.size()>max) max=map.size();
}
return max;
}
}
解法二：滑动窗口法
所谓滑动窗口，其实就是在字符串中先选定一段，把这段作为一个可以滑动的窗口，这个窗口类似于队列，每次判断队列中字符是否满足题目条件，不满足即向左滑动（这是整体情况下 一般是向左 自然 也可以只会滑动右边界），滑动窗口的时候，自然左边会少一位，右边会多一位。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
int left = 0;
for(int i = 0; i < s.length(); i ++){
if(map.containsKey(s.charAt(i))){ //判断是否存在已有队列中
//有的话 找到map中该重复的元素的索引位置 判断两者索引大小 通过对索引的判断 不断向右滑动变化起点
left = Math.max(left,map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i),i);//不存在则添加到map中
max = Math.max(max,i-left+1); // 更新最大长度
}
return max;
}
}
第二题 找到字符串中所有字母异位词
思路
和第一题类似 也是遍历找子串 只是这个题目判断依据 不是重复 而是找异位词 异位词的定义我们之前也遇到过 简单来说 就是字母组成一样 如果是异位词 那么排序后的字符串两者一定是一样的 所以我们对其的判断方式就是排序后是否一样 那么这道题的解题思路就很明确
需要注意字符串长度 判null等特殊情况
解法一：暴力法
同样的 直接暴力遍历 然后判断是否为异位词就行即可
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if(s==null||p.length()>s.length()) return new ArrayList<>();
char[] pArray = p.toCharArray();
Arrays.sort(pArray);
ArrayList<Integer> list = new ArrayList<>();
int i=0;int l=p.length();
// abvdef ab
for(i=0;i<=s.length()-l;i++){
char[] sArray = s.substring(i, i + l).toCharArray();
Arrays.sort(sArray);
if(String.valueOf(pArray).equals(String.valueOf(sArray))){
list.add(i);
}
}
return list;
}
}我们是采用排序的方式进行判断异位词 当然也可以采用哈希表映射 统计字母次数的方式 代码如下
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;
}
}
解法二：滑动窗口法
我们不再分别统计滑动窗口和字符串 p 中每种字母的数量，而是统计滑动窗口和字符串 p 中每种字母数量的差；并引入变量 differ来记录当前窗口与字符串 p 中数量不同的字母的个数，并在滑动窗口的过程中维护它。
在判断滑动窗口中每种字母的数量与字符串 ppp 中每种字母的数量是否相同时，只需要判断 differ是否为零即可
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<Integer>();
int sLen = s.length();
int pLen = p.length();
if(sLen < pLen) {
return res;
}
//表示字母出现次数差距
//count[x] = 0 表示 s与p中字母x出现次数相同 都出现了n次(n>=0)
//count[x] = n 表示 在s中字母x出现次数比p多 多出现了n次(n>0)
//count[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次(n>0)
int[] count = new int[26];
for(int i = 0; i < pLen; i++){
++count[s.charAt(i)-'a'];
--count[p.charAt(i)-'a'];
}
//表示字母差异个数
int differ = 0;
for(int j = 0; j < 26; j++){
if(count[j]!=0)++differ;
}
if(differ==0){
res.add(0);
}
//向右滑动
for(int i = 0; i < sLen - pLen; i++){
//缩减时只考虑count[x]==1与count[x]==0的情况
//因为缩减时字母x减少，count[x]会减去1
//(1)count[x]==1时(次数差距1次，不相同)
//count[x]==0 -> 次数相同 -> 不相同变相同，字母差异个数减少1 -> differ--
//(2)count[x]==0时(次数相同)
//count[x]==-1 -> 次数差距变为1次->相同变不相同 ，字母差异个数增加1 -> differ++
//(3)count[x]==-1时(次数不相同) -> count[x]==-2 次数还是不相同-> 字母差异数不变
//(4)count[x]==2时(次数不相同) -> count[x]==1 次数还是不相同-> 字母差异数不变
//左缩减一位，i
if (count[s.charAt(i) - 'a'] == 1) {
//窗口中s子串左边减少一个s[i]的数量(把原来多出来的1个s[i]去掉，变得相同)
//两个字符串字母差距缩小
--differ;
} else if (count[s.charAt(i) - 'a'] == 0) {
//窗口中s子串左边减少一个s[i]的数量(把原来相同数量的s[i]的减少了1个，数量变得不相同)
//两个字符串字母差距增大
++differ;
}
//窗口中s子串左边减少一个字母s[i]
--count[s.charAt(i) - 'a'];
//添加时只考虑count[x]==-1与count[x]==0的情况，原因分析与缩减时类似
//右添加一位，i+pLen
if (count[s.charAt(i + pLen) - 'a'] == -1) {
//窗口中s子串右边增加一个s[i+pLen]的数量(把原来缺少的1个s[i]加上，数量变得相同)
//两个字符串字母差距缩小
--differ;
} else if (count[s.charAt(i + pLen) - 'a'] == 0) {
//窗口中s子串右边增加一个s[i+pLen]的数量(把原来相同数量的s[i]多加了1个，变得不相同)
//两个字符串字母差距增大
++differ;
}
//窗口中s子串右边增加一个字母s[i+pLen]
++count[s.charAt(i + pLen) - 'a'];
//两个字符串字母差距为0
if (differ == 0) {
res.add(i + 1);
}
}
return res;
}
}
