数组中的问题其实最常见

• 通过基础问题，掌握写出正确算法的“秘诀”
• 巧妙使用双索引技术，解决复杂问题
• 对撞指针- 滑动窗口

1 从二分查找法看如何写出正确的程序

本节学习重点：处理边界问题！

• 1.确定边界范围方法，先用区间表示，即明确范围的数学定义，后用代码表示；
• 2.在循环里维护循环不变量，能保证算法的正确性，即这里的“在[l…r]的范围里寻找target”；
• 3.重新理解一些基础算法当中的循环不变量。截图代码中：while(l<=r)、l=mid+1、r=mid-1都是在维护循环不变量“在[l…r]的范围里寻找target”。

2 写程序与调试程序

写程序：

• 1、明确变量的含义，包含的范围区间
• 2、循环不变量(比如Java的list的length的获取)，保证变量和区间在循环时保持正确

调程序：

• 1、小数据量测试：边界条件，特殊情况，错误例子。
• 2、大数据量测试：性能和大数据量测试。

3~4 283号问题Move Zeros

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]说明:必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

解法1：最简单解法，常规思维

package Chapter03Array.MoveZeros;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/ @note      : 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。*              解决思路：遍历整个数组，把非零地先存起来，然后在赋值回nums，把剩下的位置补零即可            * @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/19 18:53*/
class Solution {public void moveZeroes(int[] nums) {// list初始化最好指定大小List<Integer> numList = new ArrayList<>(nums.length);for (int num : nums) {if (num != 0) {numList.add(num);}}for (int i = numList.size(); i < nums.length; i++) {numList.add(0);}for (int i = 0; i < nums.length; i++) {nums[i] = numList.get(i);}}public static void main(String[] args) {int[] nums = {0,1,0,3,12};new Solution().moveZeroes(nums);System.out.println(Arrays.toString(nums));}
}

解法2：双指针法，不用额外空间

package Chapter03Array.MoveZeros;import java.util.Arrays;/ @note      : 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。*              简化解法：双指针法，把非零元素不断前移，把剩下的补零。没有使用任何辅助空间* @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/19 18:53*/
class Solution {/* 简化解法：双指针法，把非零元素不断前移，把剩下的补零。没有使用任何辅助空间*/public void moveZeroes(int[] nums) {// k代表nums中，[0...k)的元素均为非0元素int k = 0;// 遍历到第i个元素后，保证[0...i)中所有非0元素都按照顺序排列在[0...k)中for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {nums[k++] = nums[i];}}// 将nums中的剩余位置补零for (int i = k; i < nums.length; i++) {nums[i] = 0;}}public static void main(String[] args) {int[] nums = {0, 1, 0, 3, 12};new Solution2().moveZeroes(nums);System.out.println(Arrays.toString(nums));}
}

解法3：对换法，非零元素和零元素对换位置，不需要额外的空间和时间，最优

package Chapter03Array.MoveZeros;import java.util.Arrays;/ @note      : 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。* @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/19 18:53*/
class Solution3 {/* 简化解法：对外交换法，零和非零元素对位交换，不需要额外空间和时间，最为简单*/public void moveZeroes(int[] nums) {// k代表nums中，[0...k)的元素均为非0元素int k = 0;// 遍历到第i个元素后，保证[0...i)中所有非0元素都按照顺序排列在[0...k)中for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {// 零和非零元素对位交换int tmp = nums[k];nums[k] = nums[i];nums[i] = tmp;k++;}}}public static void main(String[] args) {int[] nums = {0, 1, 0, 3, 12};new Solution3().moveZeroes(nums);System.out.println(Arrays.toString(nums));}
}

LeetCode上更多同类型问题

• 27 Remove Element

  给定一个数组nums和一个数值val，将数组中所有等于val的元素删除，并返回剩余的元素个数。
  如nums = [3, 2, 2, 3], val = 3；
  返回2，且nums中前两个元素为2
  

  注意事项：

  • 如何定义删除？从数组中去除？还是放在数组末尾？
  • 剩余元素的排列是否要保证原有的相对顺序？
  • 是否有空间复杂度的要求？ O(1)

    class Solution {public int removeElement(int[] nums, int val) {int k = 0;for(int i = 0; i < nums.length; i++){if(nums[i] != val){nums[k++] = nums[i];}}return k;}}
  

• 26 Remove Duplicated from Sorted Array

  给定一个有序数组，对数组中的元素去重，使得原数组的每个元素只有一个。返回去重后数组的长度值
  如 nums = [1, 1, 2]，
  结果应返回2，且nums的前两个元素为1和2
  

  注意事项：

  • 如何定义删除？从数组中去除？还是放在数组末尾？
  • 剩余元素的排列是否要保证原有的相对顺序？
  • 是否有空间复杂度的要求？ O(1)

    class Solution {public int removeDuplicates(int[] nums) {int k = 0;for(int i = 1; i< nums.length; i++){if(nums[i] != nums[k]){ // 有序数组，所以直接和前面的比较就知道有没有排序了nums[++k] = nums[i];}}return k + 1; // k从0开始，所以数组长度最后要+1}
    }
    

• 80 Remove Duplicated from Sorted Array II

  给定一个有序数组，对数组中的元素去重，使得原数组的每个元素最多保留两个。返回去重后数组的长度值
  如 nums = [1, 1, 1, 2, 2, 3]，
  结果应返回5，且nums的前五个元素为1, 1, 2, 2, 3
  

  class Solution {public int removeDuplicates(int[] nums) {int k = 1;// 前2位无论如何都是要加入地，所以直接跳过接口for(int i = 2; i < nums.length; i++){if(nums[i] != nums[k]){nums[++k] = nums[i];}else {// 相邻的相等，还要再往前判断一位if(nums[i] != nums[k - 1]){nums[++k] = nums[i];}}}return k + 1;}
  }
  

5 三路快排partition思路的应用 Sort Color

LeetCode75号问题 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:
不能使用代码库中的排序函数来解决这道题。示例:输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

解法1：系统自带的Arrays.sort()方法直接排好了

解法2：使用计数排序的两趟扫描算法

package Chapter03Array.SortColors;import java.util.Arrays;/ 题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。* 思路：使用计数排序的两趟扫描算法 @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/19 20:05*/
class Solution {public void sortColors(int[] nums) {int[] count = {0, 0, 0};for (int i = 0; i < nums.length; i++) {count[nums[i]]++;}Arrays.fill(nums, 0, count[0], 0);Arrays.fill(nums, count[0], count[0] + count[1], 1);Arrays.fill(nums, count[0] + count[1], nums.length, 2);}public static void main(String[] args) {int[] nums = {2, 0, 2, 1, 1, 0};new Solution().sortColors(nums);System.out.println(Arrays.toString(nums));}
}

解法3：三路快排法

package Chapter03Array.SortColors;import java.util.Arrays;/ 题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。* 思路：三路快速排序，按照0、1、2把数据分成三份，通过数据交换即可一次循环完成排序 @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/19 20:05*/
class Solution2 {void swap(int[] nums, int i, int j) {int tmp = nums[j];nums[j] = nums[i];nums[i] = tmp;}public void sortColors(int[] nums) {// nums[0...zero] == 0int zero = -1;// nums[two...n-1] == 2int two = nums.length;for (int i = 0; i < two; ) {if (nums[i] == 1) {i++;} else if (nums[i] == 2) {// 等于2时i不需要继续前移swap(nums, i, --two);} else {// nums[i] ==0swap(nums, ++zero, i++);}}}public static void main(String[] args) {int[] nums = {2, 0, 2, 1, 1, 0};new Solution2().sortColors(nums);System.out.println(Arrays.toString(nums));}
}

更多题目

• 88 Merge Sorted Array：给定两个有序整型数组nums1, nums2，将nums2的元素归并到nums1中

  class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {// 1.递归终止条件if(n == 0){// nums2为空时，nums1还有元素，调整完毕，nums1既是想要的return;}if(m == 0){// nums1为空时，nums2还有元素，直接把nums2剩下的元素全都覆盖到nums1中即可for(int i = 0; i < n; i++){nums1[i] = nums2[i];}return;}// 2.递归的具体逻辑// nums2和nums1都不为空时，需要比较最后一个元素，决定nums1最后插入哪个元素if(nums2[n - 1] > nums1[m - 1]){// nums2的最后一个元素大于nums1的最后一个元素，则nums1最后的元素取nums2的nums1[m + n -1] = nums2[n - 1];// nums2少了一个元素，继续往下递归merge(nums1, m, nums2, n-1);}else {// nums2的最后一个元素小于nums1的最后一个元素，则nums1最后的元素取nums1的nums1[m + n -1] = nums1[m - 1];// nums1少了一个元素，继续往下递归merge(nums1, m-1, nums2, n);}}
  }
  

• 215 Kth Largest Element in an Array

  在一个整数序列中寻找第k大的元素
  如给定数组 [3, 2, 1, 5, 6, 4], k = 2， 结果为5
  利用快排partition中，将pivot放置在了其正确的位置上的性质
  

  解题思路：维护一个大小为k的最小堆，遍历一遍数组，最后的最小堆堆顶元素就是第k大的元素

  class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>(k);for (int num : nums) {if (pq.size() < k) {pq.offer(num);} else {pq.offer(num);pq.poll();}}return pq.poll();}
  }
  

6 Two Sum问题

LeetCode第1号问题 两数之和

给定一个有序整型数组和一个整数target，在其中寻找两个元素，使其和为target。返回这两个数的索引。
如numbers = [2, 7, 11, 15], target = 9
返回数字2，7的索引1, 2 (索引从1开始计算)注意：如果没有解怎样？保证有解如果有多个解怎样？返回任意解解题思路：
0.暴力解法，两层for循环，列出所有的可能，总能找出来符合条件地，不过这种方法性能太低，容易超时
1.因为是有序地，所以一个确定一个元素后，另一个元素在数组中用二分法查找
2.也可以用使用两个指针，从两边向中间靠近，直到获取nums[i] + nums[j] = target，这个方法又称对撞指针法，下面有实现

/ @Description : 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。* 可以用使用两个指针，从两边向中间靠近，直到获取nums[i] + nums[j] = target，这个方法又称对撞指针法，下面有实现* @author      : 梁山广(Liang Shan Guang)* @date        : 2019/8/19 23:48* @email       : liangshanguang2@gmail.com*/
package Chapter03.TwoSum;import java.util.Arrays;class Solution {public int[] twoSum(int[] numbers, int target) {int l = 0, r = numbers.length - 1;while (l < r) {if (numbers[l] + numbers[r] == target) {// 注意返回地是下标，而且是从1开始return new int[]{l + 1, r + 1};} else if (numbers[l] + numbers[r] < target) {l++;} else {r--;}}return null;}public static void main(String[] args) {int[] numbers = {2, 7, 11, 15};int target = 9;int[] result = new Solution().twoSum(numbers, target);System.out.println(Arrays.toString(result));}
}

扩展问题

• 125 Valid Palindrome

  // 125 Valid Palindrome
  给定一个字符串，只看其中的数字和字母，忽略大小写，判断这个字符串是否为回文串？
  “A man, a plan, a canal; Panama” - 是回文串
  “race a car” - 不是回文串注意事项：空字符串如何看？字符的定义？大小写问题
  

  class Solution {public boolean isPalindrome(String s) {s = s.toLowerCase();int l = 0;int r = s.length() - 1;while(l < r){// 只要还没相遇就接着往下走if(!Character.isLetterOrDigit(s.charAt(l))){// 左边的字符不是字母或数字l++;continue;}if(!Character.isLetterOrDigit(s.charAt(r))){// 右边的字符不是字母或数字r--;continue;}// 左右两边都是字母或数字，只要不相等就说明不是回文if(s.charAt(l) != s.charAt(r)){return false;}// 相等地话，继续向中间靠拢l++;r--;}return true;}
  }
  

• 344 Reverse String

  给定一个字符串，返回这个字符串的倒序字符串。
  - 如“hello”，返回”olleh”
  - 类似：翻转一个数组
  

  class Solution {public void reverseString(char[] s) {int l = 0;int r = s.length - 1;while(l < r){char tmp = s[l];s[l] = s[r];s[r] = tmp;l++;r--;}}
  }
  

• 345 Reverse Vowels of a String

  给定一个字符串，将该字符串中的元音字母翻转
  如：给出 ”hello”，返回”holle”
  如：给出“leetcode”，返回“leotcede”
  元音不包含y
  

  class Solution {public String reverseVowels(String s) {String vowels = "aeiouAEIOU"; // 注意大小写char[] chs = s.toCharArray();int l = 0;int r = s.length() - 1;while(l < r){// 左边不是元音字符if(!vowels.contains(String.valueOf(chs[l]))){l++;continue;}// 右边不是元音字符if(!vowels.contains(String.valueOf(chs[r]))){r--;continue;}// 左右都为元音字符char tmp = chs[l];chs[l] = chs[r];chs[r] = tmp;l++;r--;}return String.valueOf(chs);}
  }
  

• 11 Container With Most Water

  给出一个非负整数数组 a1,a2,a3,…,an；每一个整数表示一个竖立在坐标轴x位置的一堵高度为ai的“墙”，选择两堵墙，和x轴构成的容器可以容纳最多的水。
  

  /
  * 基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针，值小的指针向内移动，这样就减小了搜索空间 
  * 因为面积取决于指针的距离与值小的值乘积，如果值大的值向内移动，距离一定减小，而求面积的另外一个乘数一定小于等于值小的值，因此面积一定减小；
  * 而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历
  */
  class Solution {public int maxArea(int[] height) {int maxArea = 0;int l = 0;int r = height.length - 1;while (l < r) {int area = Math.min(height[l], height[r]) * (r - l);maxArea = Math.max(area, maxArea); // 更新最大值// height小地向内移动，贪心算法。如果求最小值就是height大地向内移动if (height[l] < height[r]) {l++;} else {r--;}}return maxArea;}
  }
  

7 滑动窗口问题

LeetCode第209号问题 长度最小的子数组

核心思想：用于求解符合条件的连续子数组问题，方法是维护一个范围[l, r)，l和r均在数组范围内，不断调整l和r使得区间内的元素满足题目要求

给定一个整型数组和一个数字s，找到数组中最短的一个连续子数组，使得连续子数组的数字和sum >= s，返回这个最短的连续子数组的长度值
如，给定数组[2, 3, 1, 2, 4, 3], s = 7
答案为[4, 3]，返回2注意：什么叫子数组如果没有解怎么办？返回0

方法1：暴力解

遍历所有的连续子数组[i…j]，计算其和sum，验证sum >= s，时间复杂度O(n^3)

方法2：滑动窗口

不算调整窗口长度来看窗口数组是否满足条件，过程中记录窗口数组的长度，不断取最小值

/ @Description : 滑动窗口问题* @author      : 梁山广(Liang Shan Guang)* @date        : 2019/8/20 07:49* @email       : liangshanguang2@gmail.com*/
package Chapter03.MinSubArrayLen;/* 时间复杂度O(n),空间复杂度O(1)*/
class Solution {public int minSubArrayLen(int s, int[] nums) {// nums[l, r)为我们的滑动窗口，左闭右开区间，初始化应该不包含任何元素int l = 0, r = -1;int sum = 0;// 后面是求最小值，所以开始要设置成最大值int minLen = nums.length + 1;while (l < nums.length) {// 因为要r++，所以务必判断r的范围if ((r + 1) < nums.length && sum < s) {// 小于要求的目标和s了，右边元素下标右移，然后计算新的数组和sumr++;sum = sum + nums[r];} else {// 大于要求地目标和s了，先减去l位置的元素，然后左边元素下标右移sum = sum - nums[l];l++;}if (sum >= s) {// 满足要求了就取出窗口长度,minLen = Math.min(minLen, r - l + 1);}}if (minLen == nums.length + 1) {// minLen从未更新过，说明数组中不存在子数组满足其和大于等于sreturn 0;}return minLen;}public static void main(String[] args) {int s = 11;int[] nums = {1, 2, 3, 4, 5};int minLen = new Solution().minSubArrayLen(s, nums);System.out.println(minLen);}
}

8 在滑动窗口中做记录 Longest Substring Without Repeating Characters

LeetCode第3号问题 无重复字符的最长子串，此题中引入了频率数组用于统计各个字符的出现次数

在一个字符串中寻找没有重复字母的最长子串，返回其长度。
如”abcabcbb”，则结果为”abc”，长度为3
如”bbbbb”，则结果为”b”，长度为1
如”pwwkew”，则结果为”wke”，长度为3注意：字符集？只有字母？数字+字母？ASCII？大小写是否敏感？

package Chapter03Array.LongestSubString;import java.util.Arrays;/ @note      : 在一个字符串中寻找没有重复字母的最长子串* @author    : l00379880 梁山广* @version   : V1.0 at 2019/8/20 9:32*/
public class Solution {public int lengthOfLongestSubstring(String s) {// freq表示所有的ASCII码字符对应的频率int[] freq = new int[256];Arrays.fill(freq, 0);// 滑动窗口为s[l...r)左闭右开区间int l = 0, r = -1;// 要求最大值，就得初始化为最小值int maxLen = 0;while (l < s.length()) {if (r + 1 < s.length() && freq[s.charAt(r + 1)] == 0) {// 最右侧的字符还没统计过频率，那么就把最右侧的字符放入统计数组freqr++;freq[s.charAt(r)]++;} else {// 已经到最右侧或者最右侧的字符已经统计过频率了非0了，那么就把最左侧的字符右移，右边界不进行扩展freq[s.charAt(l)]--;l++;}maxLen = Math.max(maxLen, r - l + 1);}return maxLen;}public static void main(String[] args) {String s = "abcabcbb";System.out.println(new Solution().lengthOfLongestSubstring(s));}
}

滑动窗口的其他相关问题

• 438.找到字符串中所有字母异位词

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {int[] freq = new int[256];/* 判断[l, r)的区间是否满足要求：即使anagrams @param l 左边界* @param r 右边界* @param s 原字符串* @return [l, r)是否满足要求*/boolean isAnagrams(int l, int r, String s, String p) {int[] freqTmp = new int[256];Arrays.fill(freqTmp, 0);for (int i = l; i < r; i++) {freqTmp[s.charAt(i)] += 1;}for (int i = 0; i < p.length(); i++) {if (freqTmp[p.charAt(i)] != freq[p.charAt(i)]) {return false;}}return true;}public List<Integer> findAnagrams(String s, String p) {// 初始化为-1，-1表示时不需要查找的字符Arrays.fill(freq, 0);// 更新在p中的字符for (int i = 0; i < p.length(); i++) {freq[p.charAt(i)] += 1;}// 存储符合条件的起始索引的列表List<Integer> indexList = new ArrayList<>();int l = 0;int r = p.length();// 右边界还没滑动到末尾时就一直往后滑动while (r <= s.length()) {if (isAnagrams(l, r, s, p)) {indexList.add(l);}l++;r++;}return indexList;}public static void main(String[] args) {String s = "baa";String p = "aa";List<Integer> anagrams = new Solution().findAnagrams(s, p);System.out.println(anagrams);}
}

优化1：

class Solution {public List<Integer> findAnagrams(String s, String p) {// 存储符合条件的起始索引的列表List<Integer> indexList = new ArrayList<>();if ("".equals(s) || "".equals(p) || s.length() < p.length()) {return indexList;}int[] freq = new int[256];int[] freqTmp = new int[256];Arrays.fill(freq, 0);Arrays.fill(freqTmp, 0);// 更新在p中的字符for (int i = 0; i < p.length(); i++) {freq[p.charAt(i)] += 1;// 初始化窗口内的字符频率freqTmp[s.charAt(i)] += 1;}int l = 0;int r = p.length();// 右边界还没滑动到末尾时就一直往后滑动while (r <= s.length()) {boolean find = true;for (int i = l; i < r; i++) {if (freqTmp[s.charAt(i)] != freq[s.charAt(i)]) {find = false;break;}}if (find) {indexList.add(l);}if (r + 1 > s.length()) {break;}// 窗口向后移动,注意区间是左闭右开[l...r)freqTmp[s.charAt(l)] -= 1;freqTmp[s.charAt(r)] += 1;l++;r++;}return indexList;}
}

• 76.最小覆盖子串

/ @Description : LeetCode 76号问题：最小覆盖字符串* @author      : 梁山广(Liang Shan Guang)* @date        : 2020/1/15 23:34* @email       : liangshanguang2@gmail.com*/
package Chapter03.LeetCode76;class Solution {public String minWindow(String s, String p) {int sLen = s.length();int pLen = p.length();if ("".equals(s) || "".equals(p) || sLen < pLen) {return "";}// s="ab" p="Aif (pLen == 1) {if (s.contains(p)) {return p;} else {return "";}}int[] freq = new int[256];int[] freqTmp = new int[256];// 更新在p中的字符for (int i = 0; i < pLen; i++) {freq[p.charAt(i)] += 1;// 初始化窗口内的字符频率freqTmp[s.charAt(i)] += 1;}int l = 0;int r = pLen;int lMin = 0;int rMin = pLen;// 找最小时，初始应为最大值int min = Integer.MAX_VALUE;// 右边界还没滑动到末尾时就一直往后滑动while (r <= sLen) {boolean find = true;for (int i = 0; i < pLen; i++) {if (freqTmp[p.charAt(i)] == 0) {// 有一个p中的字母在s中找不到，直接跳出find = false;break;} else {// 能找到但是频率小，出现频率大于等于可以if (freqTmp[p.charAt(i)] < freq[p.charAt(i)]) {find = false;break;}}}if (find) {// 找到了符合条件的字符串if ((r - l) < min) {// 新的区间小于初始化地最小区间才需要更新min = r - l;lMin = l;rMin = r;}}if (freq[s.charAt(l)] == 0) {// 最左边的字母不在p中，此时窗口宽度必须必p的长度大，这样左边的l才可以右移if (r - l > pLen) {// 在维持窗口宽度的前提下，左边界l可以向右移动地freqTmp[s.charAt(l)] -= 1;l++;} else {// 长度不够，r必须先往右侧移动// 必须放在这里~~否则会提前退出地if (r + 1 > sLen) {break;}freqTmp[s.charAt(r)] += 1;r++;}} else {// 最左边的元素在p中，同时它的频率大于在p中的频率了，左边界l一定是可以向右移动地，需要更新freqTmpif (freqTmp[s.charAt(l)] > freq[s.charAt(l)]) {freqTmp[s.charAt(l)] -= 1;l++;} else {// 必须放在这里~~否则会提前退出地if (r + 1 > sLen) {break;}// 其他情况下只能右侧元素往右移动，并更新频率freqTmp[s.charAt(r)] += 1;r++;}}}if (min == Integer.MAX_VALUE) {return "";} else {return s.substring(lMin, rMin);}}/* 想到的异常用例：* S = "aa", T = "a"  ==> "a"* S = "abc", T = "acd"  ==> ""* S = "abc", T = "cba"  ==> abc* S = "bbaa", T = "aba"  ==>baa* S = "aaaaaaaaaaaabbbbbcdd", T = "abcdd"  ==> abbbbbcdd* S = "aabAA", T = "BB"*/public static void main(String[] args) {String S = "aabAA";// cba、acd都测测String T = "BB";System.out.println(new Solution().minWindow(S, T));}
}