題目
實現(xiàn)函數(shù)：輸入一個字符串str菱属，一個int值k汞幢，輸出str中最多含有k個字符的子串最大長度.例如str="aabc"驼鹅，k="2"，則輸出3森篷，因為最長含2個字符的子串是"aab"
解決
- 暴力法
i遍歷字符串输钩，考察以i開頭的子串滿足條件的最大長度，時間復(fù)雜度為O(n^2) - 暴力法
遍歷str的所有子串（從長到短）仲智，考察其是否滿足條件买乃，時間復(fù)雜度為O(n^2) - HashMap+快慢指針
利用map記錄子串中每個字符的數(shù)量、利用快慢指針進行遍歷钓辆，分別代表子串的結(jié)尾j與開頭i
快指針將指向的字符計入map剪验，若此時map.size>k，則移動慢指針（砍掉子串的開頭）岩馍，直至map.size()恢復(fù)正常碉咆，快指針繼續(xù)向前（增加子串的結(jié)尾）。這一過程中j-i+1的最大值即為答案
代碼
public static int find(String str, int k){
HashMap<Character,Integer> map = new HashMap<>();
int max = 0;
for (int j=0,i=0;j<str.length();j++){
char toPut = str.charAt(j);
map.put(toPut,map.getOrDefault(toPut, 0)+1);
while (map.size()>k){
char temp = str.charAt(i);
map.put(temp, map.get(temp)-1);//利用map鍵唯一的特點蛀恩，通過put實現(xiàn)值修改
if (map.get(temp)==0)
map.remove(temp);
i ++;
}
max = Math.max(max,j-i+1);
}
return max;
}
