无重复字符的最长子串
解法一
暴力
使用双层for循环来遍历，第一层for循环的是开头，第二层的是结尾
使用HashSet来保存字符，如果HashSet中存在时，add操作就会返回false，直接结束本次循环
class Solution { public int lengthOfLongestSubstring(String s) { int len = s.length(); if(len == 0 || len == 1)return len; int ans = 0; for(int i = 0;i < len;i++){ int t = 1; HashSet<Character> set = new HashSet<>(); set.add(s.charAt(i)); for(int j = i+1;j < len;j++){ if(!set.add(s.charAt(j))){ break; } t++; } ans = Math.max(t,ans); } return ans; } }
解法二
滑动窗口
维护滑动窗口中的值是一定没有重复元素的
右边界就是当前循环的i
左边界最开始就是left = 0；
然后如果滑动窗口中有当前值就把left移动到上一个当前值的上一个位置
注意： 我滑动窗口用的HashMap所以left需要比较left与当前值的上一个位置的大小
class Solution { public int lengthOfLongestSubstring(String s) { int len = s.length(); if(len == 0 || len == 1)return len; int ans = 0; int left = 0; HashMap<Character,Integer> map = new HashMap<>(); for(int i = 0;i < len;i++){ if(map.containsKey(s.charAt(i))){ left = Math.max(left,map.get(s.charAt(i))+1); } map.put(s.charAt(i),i); ans = Math.max(ans,i-left+1); } return ans; } }
最长连续序列
解法一
暴力
把所有数据全加入到Set集合
不断枚举当前值的下一个是否在Set中存在，如果存在就一直枚举下去
剪枝： 如果set中存在当前值num的减一，那么不向后遍历这个数，因为他总是短于num-1开始的数字
举例： 假如num ~ num+n 是一段答案那么num-1 ~ num+n是优于num~num+n的
找到字符串中所有字母异位词
解法一
滑动窗口
class Solution { public List<Integer> findAnagrams(String s, String p) { int slen = s.length(); int plen = p.length(); List<Integer> list = new ArrayList<>(); if(slen < plen) return list; int []parr = new int[26]; int []sarr = new int[26]; for(int i = 0;i < plen;i++){ parr[p.charAt(i)-'a']++; sarr[s.charAt(i)-'a']++; } if(Arrays.equals(sarr,parr)){ list.add(0); } for(int i = 1;i <= slen-plen;i++){ sarr[s.charAt(i-1)-'a']--; sarr[s.charAt(i+plen-1)-'a']++; if(Arrays.equals(sarr,parr)){ list.add(i); } } return list; } }
