求最短/最小
一、最短且字典序最小的美丽子字符串
题意：
给你一个二进制字符串 s 和一个正整数 k 。如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。返回长度等于 len 且字典序 最小 的美丽子字符串。
eg:字典序 abcd/abcc d>c 所以abcc的字典序更小
思路：
1.首先判断字符串中的1是否>=k,如果小于k，那么直接返回""
2.如果大于k，那么最小美丽字符串的开头一定是以'1'开头的。
3.遍历字符串的时候，只要count1>k或者s.charAt(left)=='0'的时候，左边界就要移动
while(count>k||s.charAt(left)=='0'){if(s.charAt(left)=='1')count--;left++;}4.当count1==k的时候，此时就是收割结果的时候；题目中要求我们获得最短并且字典序最小。那我们先判断长短，然后再判断字典序。
if(count==k){String str=s.substring(left,right+1);if(str.length()<res.length()||str.length()==res.length()&&str.compareTo(res)<0){res=str;}}代码：
class Solution {public String shortestBeautifulSubstring(String s, int k) {if(s.replace("0","").length()<k)return "";int left=0;int right=0;int count=0;String res=s;while(right<s.length()){char ch=s.charAt(right);if(ch=='1')count++;while(count>k||s.charAt(left)=='0'){if(s.charAt(left)=='1')count--;left++;}if(count==k){String str=s.substring(left,right+1);if(str.length()<res.length()||str.length()==res.length()&&str.compareTo(res)<0){res=str;}}right++;}return res;}
}二、替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。请返回待替换子串的最小可能长度。
输入：s = "QQQQ" 输出：3 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
思路：
要返回替换子串的最小可能长度。替换子串+不替换子串=子串。
不替换子串中某个字母出现的次数一定要<=k次，因为如果出现的次数>k次，那么就要出现在替换子串中了。
1.当不替换子串中字母出现的次数>k次的，将right右移，arr[s.charAt(right)]--;这样不替换子串中字母出现的次数可能会<k次。
2.当不替换子串中字母出现的次数是<=k次的，说明替换子串是符合题意的；那么left右移，不断缩小替换子串，看是否满足题意；
代码：
class Solution {public int balancedString(String s) {int[] arr = new int[26];for (int i = 0; i < s.length(); i++) {arr[s.charAt(i) - 'A']++;}int limit = s.length() / 4;int left = 0;int right = -1;int minLength = s.length();while (left < s.length()) {if (check(arr, limit)) {minLength = Math.min(minLength, right - left + 1);arr[s.charAt(left) - 'A']++;left++;} else if (right < s.length() - 1) {right++;// 因为right是从-1开始的arr[s.charAt(right) - 'A']--;} else {break;}}return minLength;}public boolean check(int[] arr, int limit) {// 要检验剩余部分的字母是否有出现>limit次的if (arr['Q' - 'A'] > limit || arr['W' - 'A'] > limit || arr['E' - 'A'] > limit || arr['R' - 'A'] > limit)return false;return true;}
}三、无限数组的最短子数组
给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。
题意：
给定一个数组nums,nums中的元素按照顺序循环放在infinite_nums中，然后在infinite_nums中找到一个最短子数组，和为target。
思路：
判断target，如果target大于nums中所有元素的和；说明子数组一定是包含整个nums的。剩下的部分可能在一个数组中，也可能分布在两个数组中，所以用剩下的target(target-sum(nums))在长度为2*nums.length的数组中去找最短子数组
代码：
class Solution {public int minSizeSubarray(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}int multi = target / sum;target = target % sum;if(target==0)return multi*nums.length;int left = 0;int right = 0;int res = Integer.MAX_VALUE;sum = 0;while (right < nums.length * 2) {sum += nums[right % nums.length];while (sum > target) {sum -= nums[left % nums.length];left++;}if (sum == target)res = Math.min(res, right - left + 1);right++;}if(res==Integer.MAX_VALUE)return -1;return res+multi*nums.length;}
}
)
)