编辑
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
一：长度最小的子数组
编辑
编辑
class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0 , right = 0 , sum = 0 , n = nums.length; int len = Integer.MAX_VALUE; for(;right < n ; right++){ //进入窗口 sum += nums[right]; while(sum >= target){ //更新值 len = Math.min(len,right - left + 1); //出窗口 sum -= nums[left]; left++; } } return len == Integer.MAX_VALUE ? 0 : len; } }
二：无重复字符的最长子串
编辑
编辑
class Solution { public int lengthOfLongestSubstring(String ss) { int left = 0 , right = 0 , ret = 0; char[] s = ss.toCharArray(); int n = s.length; int[] hash = new int[128]; while(right < n){ hash[s[right]]++; while(hash[s[right]] > 1){ hash[s[left++]]--;//出窗口 } ret = Math.max(ret , right - left + 1); right++; } return ret; } }
三：最大连续1的个数
编辑
编辑
class Solution { public int longestOnes(int[] nums, int k) { int left = 0 , right = 0 , count = 0; int n = nums.length , ret = 0; while(right < n){ if(nums[right] == 1){ right++; }else{ count++; right++; } while(count > k){ if(nums[left] == 1){ left++; }else{ count--; left++; } } ret = Math.max(ret,right-left); } return ret; } }
四：将x减到0的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
编辑
编辑
class Solution4 { public int minOperations(int[] nums, int x) { int left = 0 , right = 0 , count = 0 ,sum = 0; int n = nums.length; for(int i = 0 ; i < n ; i++){ sum += nums[i]; } int target = sum - x , tem = 0; if(target < 0){ return -1; } if(target == 0){ return n; } for(; right < n ; right++){ //进窗口不判断 tem += nums[right]; while(tem > target ){ tem -= nums[left]; left++; }//执行顺序也有讲究，最后一步判断 if(tem == target){ count = Math.max(count , right-left+1); } } if(count == 0){ return -1; } return n-count; } }
五：水果成篮
编辑
编辑
class Solution { public int totalFruit(int[] f) { Map<Integer,Integer> hash = new HashMap<Integer,Integer>(); int ret = 0; for(int left = 0 , right = 0 ; right < f.length ; right++){ //进窗口 int in = f[right]; hash.put(in,hash.getOrDefault(in,0)+1); while(hash.size() > 2){//判断 //出窗口 int out = f[left]; hash.put(out,hash.get(out)-1); if(hash.get(out) == 0){ hash.remove(out); } left++; } ret = Math.max(ret,right - left + 1); } return ret; } }
六：找到字符串中所有字母的异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
编辑
编辑
编辑
class Solution { public List<Integer> findAnagrams(String ss, String pp) { List<Integer> list = new ArrayList<Integer>(); char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); int[] hashS = new int[26]; int[] hashP = new int[26]; for(char x : p){ hashP[ x - 'a']++; } for(int right = 0 , left = 0 , count = 0 ; right < ss.length() ; right++ ){ char in = s[right]; hashS[ in - 'a']++; if(hashS[in - 'a'] <= hashP[in - 'a']){ count++;//进入的是有效字符 } char out = s[left]; if(right - left + 1 > pp.length()){ hashS[out - 'a']--; if(hashS[out - 'a'] < hashP[out - 'a']){ count--; } left++; } if(count == pp.length()){ list.add(left); } } return list; } }
七：串联所有单词的子串
编辑
编辑
class Solution8 { public List<Integer> findSubstring(String s, String[] words) { List<Integer> ret = new ArrayList<Integer>(); //先把words中的元素放到HashMap中//每个元素的长度为m，数组长度为n,记录元素种类ele Map<String,Integer> hash1 = new HashMap<String,Integer>(); int m = words[0].length() , n = words.length ,ele = 0; for(String ss : words){ hash1.put(ss,hash1.getOrDefault(ss,0)+1); } for(int i = 0 ; i < m ; i++ ){ //wc太绝了hashMap每次i移动时需要初始化一下，要不然上一次的值还存留在HashMap中 Map<String,Integer> hash2 = new HashMap<String,Integer>(); for(int left = i , right = i , count = 0 ; right + m <= s.length() ; right += m){ //进窗口 String in = s.substring(right,right+m); hash2.put(in,hash2.getOrDefault(in,0)+1); //判断count加不加 if(hash2.get(in) <= hash1.getOrDefault(in,0)){ count++; } //出窗口 while(right - left + 1 > m * n ){ String out = s.substring(left,left+m); left+=m; if(hash2.get(out) <= hash1.getOrDefault(out,0)){ count--; } hash2.put(out,hash2.get(out)-1); } if(count == n){ ret.add(left); } } } return ret; } }
八：最小覆盖子串
编辑
编辑
class Solution { public String minWindow(String ss, String tt) { //先把要找的字符tt转化为数组并放到哈希表里 char[] t = tt.toCharArray(); int[] hash1 = new int[128]; int kind = 0;//统计tt字符串中有多少种字符 for(char ch : t){ hash1[ch]++; if(hash1[ch] == 1){ kind++; } } //同样把字符ss转化为数组 char[] s = ss.toCharArray(); int[] hash2 = new int[128]; int len = Integer.MAX_VALUE; int left = 0 , right = 0 , begin = -1 ; for(int count = 0; right < s.length ; right++){ //进窗口 char in = s[right]; hash2[in]++; //判断如果直接判断两个哈希表非常耗费时间引入count if(hash1[in] == hash2[in]){ count++; } //更新结果(如果种类一直相同，那就一直出窗口所以用while) while(count == kind){ if(right - left + 1 < len){ begin = left; len = right-left+1; } //出窗口 char out = s[left++]; if(hash2[out] == hash1[out] ){//考虑两种情况，出的是有效字符还是无效字符 count--; } hash2[out]--; } } //for循环走完了一直进不去while循环，返回空字符串 if(len == Integer.MAX_VALUE){ return new String(); }else{ String ret = ss.substring(begin,begin+len); return ret; } } }
