思想right 负责探索新字符left 负责擦屁股目录LCR 008. 长度最小的子数组 - 力扣LeetCodeLCR 016. 无重复字符的最长子串 - 力扣LeetCode485. 最大连续 1 的个数 - 力扣LeetCode1004. 最大连续1的个数 III - 力扣LeetCode1658. 将 x 减到 0 的最小操作数904. 水果成篮LCR 015. 找到字符串中所有字母异位词30. 串联所有单词的子串LCR 017. 最小覆盖子串LCR 008. 长度最小的子数组 - 力扣LeetCode算法逻辑 代码演示①暴力枚举暴力枚举依赖三层for循环致力于每轮都将结果加和n^3:第一层确定left第二层确定right第三层计算[left, right]区间的元素和public int minSubArrayLen(int target, int[] nums) { int len; int min Integer.MAX_VALUE; for (int left 0; left nums.length;left) { // 每换一个 leftsum 重新归 0 // right 向右移动时直接累加 nums[right] // 避免重复求区间和直接由 n^3 到 n^2 int sum 0; for (int right left; right nums.length;right) { // int sum 0; // for (int i left; i right ; i) { // sum nums[i]; // } sum nums[right]; if (sum target){ len right - left 1; min Math.min(len, min); } } } return min Integer.MAX_VALUE ? 0 : min; }②滑动窗口双指针n注意两个步骤right不断加和扩大窗口找到目标踢出当前left这样做能尝试更小的窗口不漏解public int minSubArrayLen(int target, int[] nums){ int sum 0; int len Integer.MAX_VALUE; for (int left 0,right 0;right nums.length;right){ sum nums[right]; while (sum target){ len Math.min(len, right - left 1); sum - nums[left]; } } return len Integer.MAX_VALUE ? 0 : len; }LCR 016. 无重复字符的最长子串 - 力扣LeetCode算法逻辑A暴力枚举①双层for循环以起点left为基准用right向右扩展用HashSet存放字符②遇到重复字符就停止扩展记录当前长度然后移动left到下一个位置清空set重新开始。最终取所有长度的最大值B滑动窗口HashSet①right一直右移遇到重复字符时left右移删除冲突元素直到窗口内无重复再把当前字符加进去②这样窗口始终保持无重复且right从不回退实现 O(n) 复杂度C数组模拟哈希表①用int[128]记录字符出现次数②若hash[char] ≥ 1表示重复则移动left并减计数直到重复消除代码演示①暴力枚举public int lengthOfLongestSubstring(String s) { int size Integer.MIN_VALUE; SetCharacter set new HashSet(); for (int left 0; left s.length(); left) { for (int right left; right s.length(); right) { char r s.charAt(right); if(set.contains(r)){ break; } set.add(r); size Math.max(size,right - left 1); } set.clear(); } return size Integer.MIN_VALUE ? 0 : size; }②使用HashSet的滑动窗口:public int lengthOfLongestSubstring(String s) { int size Integer.MIN_VALUE; SetCharacter set new HashSet(); for (int left 0,right 0; right s.length(); right) { char r s.charAt(right); while (set.contains(r)){ char l s.charAt(left); set.remove(l); left; } set.add(r); size Math.max(size, set.size()); } return size Integer.MIN_VALUE ? 0 : size; }③非HashSet的滑动窗口最优解public int lengthOfLongestSubstring(String s) { int size Integer.MIN_VALUE; char []arr s.toCharArray(); int []hash new int[128]; for (int left 0,right 0; right s.length(); right) { while (hash[arr[right]] 0){ hash[arr[left]]--; left; } hash[arr[right]]; size Math.max(size, right - left 1); } return size Integer.MIN_VALUE ? 0 : size; }485. 最大连续 1 的个数 - 力扣LeetCode1004. 最大连续1的个数 III - 力扣LeetCode算法逻辑 代码演示A暴力枚举public int findMaxConsecutiveOnes(int[] nums) { int size Integer.MIN_VALUE; for (int left 0; left nums.length; left) { for (int right left; right nums.length; right) { if(nums[right] ! 0){ size Math.max(size,right - left 1); }else { break; } } } return size Integer.MIN_VALUE ? 0 : size; }B滑动窗口public int findMaxConsecutiveOnes(int[] nums) { int size Integer.MIN_VALUE; for (int left 0,right 0; right nums.length;right) { if(nums[right] 0){ left right 1; } size Math.max(size,right - left 1); } return size Integer.MIN_VALUE ? 0 : size; }A暴力枚举注意每轮开始zero清零public int longestOnes(int[] nums,int k) { int size Integer.MIN_VALUE; for (int left 0; left nums.length; left) { int zero 0; for (int right left; right nums.length; right) { if(nums[right] 0){ zero; } if(zero k){ size Math.max(size,right - left 1); }else { break; } } } return size Integer.MIN_VALUE ? 0 : size; }B滑动窗口维护一个窗口窗口内0的数量超过k时移动left缩小窗口直到0的数量重新 ≤kpublic int longestOnes(int[] nums,int k) { int size Integer.MIN_VALUE; int zero 0; for (int left 0,right 0; right nums.length;right) { if(nums[right] 0){ zero; } while (zero k){ if(nums[left] 0){ zero--; } left; } size Math.max(size,right - left 1); } return size Integer.MIN_VALUE ? 0 : size; }1658. 将 x 减到 0 的最小操作数算法逻辑 代码演示A暴力枚举O(n³) 枚举左边几个 右边几个 每次重新求和public int minOperations(int[] nums, int x) { int min Integer.MAX_VALUE; for (int leftCount 0; leftCount nums.length; leftCount) { for (int rightCount 0; rightCount nums.length - leftCount; rightCount) { int sum 0; for (int i 0; i leftCount; i) { sum nums[i]; } for (int i 0; i rightCount; i) { sum nums[nums.length - 1 - i]; } if(sum x){ min Math.min(min,leftCount rightCount); } } } return min Integer.MAX_VALUE ? -1 : min; }B暴力枚举O(n²) 仍然枚举左右数量 但是 leftSum / rightSum 累加不重复求和public int minOperations(int[] nums, int x) { int min Integer.MAX_VALUE; int leftSum 0; for (int leftCount 0; leftCount nums.length; leftCount) { int rightSum 0; for (int rightCount 0;rightCount nums.length - leftCount;rightCount) { if(leftSum rightSum x){ min Math.min(min,leftCount rightCount); } //指定条件防止最后一次循环越界 if(rightCount nums.length - leftCount){ rightSum nums[nums.length - 1 - rightCount]; } } //在最后加和 //指定条件防止最后一次循环越界 if(leftCount nums.length){ leftSum nums[leftCount]; } } return min Integer.MAX_VALUE ? -1 : min; }C滑动窗口O(n) 反向思考删除两边和 x保留中间和 totalSum - x寻找最长连续子数组返回最小左右操作数量public int minOperations(int[] nums, int x) { int totalSum 0; for(int num : nums){ totalSum num; } int target totalSum - x; if(target 0){ return -1; } int sum 0; int maxLen Integer.MIN_VALUE; for (int left 0,right 0; right nums.length; right) { sum nums[right]; while (sum target){ sum - nums[left]; left; } if(sum target){ maxLen Math.max(maxLen,right - left 1); } } return maxLen Integer.MIN_VALUE ? -1 : nums.length - maxLen; }904. 水果成篮算法逻辑 代码演示A暴力枚举① 固定left让right不断向右扩每次统计窗口内水果种类② 种类 ≤ 2 就更新最大长度 2 就停止换下一个 left 重新枚举。public int totalFruit(int[] fruits) { int max Integer.MIN_VALUE; for (int left 0; left fruits.length; left) { HashSetInteger hash new HashSet(); for (int right left; right fruits.length; right) { //数组值代表种类 hash.add(fruits[right]); if(hash.size() 2){ max Math.max(max, right - left 1); }else { break; } } } return max Integer.MIN_VALUE ? 0 : max; }(数组模拟)public int totalFruit(int[] fruits) { int max Integer.MIN_VALUE; for (int left 0; left fruits.length; left) { int []hash new int[100000]; int sort 0; for (int right left; right fruits.length; right) { //种类 if(hash[fruits[right]] 0){ sort; } hash[fruits[right]]; if(sort 2){ max Math.max(max, right - left 1); }else { break; } } } return max Integer.MIN_VALUE ? 0 : max; }B滑动窗口① right不断向右扩并加入水果② 如果种类 2就移动 left 缩小窗口直到重新只剩两种水果再更新最大长度。public int totalFruit(int[] fruits) { int max Integer.MIN_VALUE; HashMapInteger,Integer hash new HashMap(); for (int left 0,right 0; right fruits.length; right) { // 数组值代表种类 // right 进来可能第一次出现 hash.put(fruits[right], hash.getOrDefault(fruits[right],0) 1); while (hash.size() 2){ // left 出去肯定已经存在 hash.put(fruits[left],hash.get(fruits[left]) - 1); if(hash.get(fruits[left]) 0){ hash.remove(fruits[left]); } left; } max Math.max(max,right - left 1); } return max Integer.MIN_VALUE ? 0 : max; }C哈希模拟数组需要自己维护水果种类public int totalFruit(int[] fruits) { int max Integer.MIN_VALUE; int []hash new int[100000]; int sort 0; for (int left 0,right 0; right fruits.length; right) { if(hash[fruits[right]] 0){ sort; } hash[fruits[right]]; while (sort 2){ hash[fruits[left]]--; if(hash[fruits[left]] 0){ sort--; } left; } max Math.max(max,right - left 1); } return max Integer.MIN_VALUE ? 0 : max; }LCR 015. 找到字符串中所有字母异位词算法逻辑 代码演示A暴力枚举每换一个 left都重新统计整个窗口public ListInteger findAnagrams(String s, String p) { char []arr1 s.toCharArray(); char []arr2 p.toCharArray(); ListInteger list new ArrayList(); int []hash2 new int[128]; for (int i 0; i p.length(); i) { hash2[arr2[i]]; } for (int left 0; left s.length() - p.length(); left) { int []hash1 new int[128]; //注意此处right的范围 for (int right left; right left p.length(); right) { hash1[arr1[right]]; } if(Arrays.equals(hash1,hash2)){ list.add(left); } } return list; }B滑动窗口right 进一个1left 出一个-1复用上一个窗口的数据public ListInteger findAnagrams(String s, String p) { char []arr1 s.toCharArray(); char []arr2 p.toCharArray(); ListInteger list new ArrayList(); int []hash2 new int[128]; for (int i 0; i p.length(); i) { hash2[arr2[i]]; } int []hash1 new int[128]; for (int left 0,right 0; right s.length(); right) { //注意此处right的范围 hash1[arr1[right]]; while (right - left 1 p.length()){ hash1[arr1[left]]--; left; } if(Arrays.equals(hash1,hash2)){ list.add(left); } } return list; }30. 串联所有单词的子串LCR 017. 最小覆盖子串本专题完