進撃の指針
209. Minimum Size Subarray Sum
i和j都不需要回滚，时间复杂度是O(n)。
这种看起来有点 greedy 味道的双指针都不同程度上利用后面状态的增长性质，直接排除一些元素，减少搜索范围。
只有全为正数的情况下，我们才能这么做。
在这道题里，如果 [i - j] 的 subarray 已经 >= target 了，考虑任何 j 以后的元素都是没有意义的，因为数组都是正数，依然会 >= target，长度还一定比当前的长。
和sliding window不一样，sliding window是固定窗口大小的。
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) return 0;
int min = Integer.MAX_VALUE;
int j = 0;
int sum = 0;
for (int i = 0; i < nums.length; ++i) {
while (j < nums.length) {
if (sum < s) {
sum += nums[j++];
} else break;
}
if (sum >= s) {
min = Math.min(min, j - i);
}
sum -= nums[i];
}
if (min == Integer.MAX_VALUE) return 0;
return min;
}
}
3. Longest Substring Without Repeating Characters
这题和上一道很像，虽然我先做的是这道。一个boolean数组来保证不会出现重复。
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) return s.length();
int max = 1;
int j = 0;
boolean[] hash = new boolean[256];
for (int i = 0; i < s.length(); ++i) {
while (j < s.length()) {
if (!hash[s.charAt(j)]) {
hash[s.charAt(j++)] = true;
} else break;
}
max = Math.max(max, j - i);
hash[s.charAt(i)] = false;
}
return max;
}
}
76. Minimum Window Substring
这道题和前面的思想是一致的，对于判断条件的处理有一些变化。
首先我们要进行预处理，对于source和target要有两个hash数组。
因为我们不关心顺序，只关心每个字符的出现次数，也就是说如果target中有某个字符出现了两次以上，那么source中这个字符的出现次数必须大于target中的次数，这样的话，我们就不能用boolean数组了，要用int数组，而且判断出现次数多少写成了额外的函数每次去调用。
public class Solution {
public String minWindow(String s, String t) {
String result = "";
int[] hashs = new int[256];
int[] hasht = new int[256];
for (int i = 0; i < t.length(); ++i) {
hasht[t.charAt(i)]++;
}
int i = 0;
int j = 0;
int min = Integer.MAX_VALUE;
for (i = 0; i < s.length(); ++i) {
while (j < s.length()) {
if (valid(hashs, hasht)) break;
hashs[s.charAt(j)]++;
j++;
}
if (valid(hashs, hasht)) {
if (min > j - i) {
min = j - i;
result = s.substring(i, j);
}
}
hashs[s.charAt(i)]--;
}
return result;
}
private boolean valid(int[] hashs, int[] hasht) {
for (int i = 0; i < hashs.length; ++i) {
if (hasht[i] > hashs[i]) return false;
}
return true;
}
}
567. Permutation in String
LC第30周的weekly contest第三题，7分。
和上一道题76几乎相同的思路和解法，刘总说同样的代码TLE了，不知道为什么我AC了。
思路和解法是一样的，但是我用的hashmap去存的count，因此遇到匹配超长字符串就TLE了，后来换成array去存count就没问题了。
另外还有重要的一点，我array开始是用的一个array A，先array A++初始化，匹配前复制给array B，碰到匹配的直接array B--。但是因为数组是传引用，所以array B修改的话，array A也受影响。就只能新建一个数组，碰到匹配的，新数组++，再与array A比较。
public class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] array = s1.toCharArray();
int[] source = new int[26];
int[] target = new int[26];
for (char ch : array) {
target[ch - 'a']++;
}
int i = 0;
int j = 0;
int count = 0;
for (i = 0; i < s2.length(); ++i) {
while (!valid(source, target) && j < s2.length()) {
source[s2.charAt(j) - 'a']++;
j++;
count++;
}
if (valid(source, target) && count == s1.length()) return true;
source[s2.charAt(i) - 'a']--;
count--;
}
return false;
}
private boolean valid(int[] source, int[] target) {
for (int i = 0; i < source.length; ++i) {
if (source[i] < target[i]) return false;
}
return true;
}
}
159. Longest Substring with At Most Two Distinct Characters
这道题不错，和之前的算法逻辑基本一样，不同的是，前面要求重复尽量少，这道题要重复尽量多，根据不同的要求，我们选择用boolean数组，int数组。int数组默认初始化全为0。这样的话每次归零我们就知道当前这个字符不存在了，用一个distinctCount来决定一个substring中有多少个不同的字符。
思想是不变的，前向型双指针的题目多练一练就有感觉了。
别忘了j++，写错了一回。
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if (s.length() <= 2) return s.length();
int[] hash = new int[256];
int max = 2;
int distinctCount = 0;
int j = 0;
for(int i = 0; i < s.length(); i++){
while(j < s.length()){
if(distinctCount == 2 && hash[s.charAt(j)] == 0) break;
if(hash[s.charAt(j)] == 0) distinctCount ++;
hash[s.charAt(j++)]++;
}
if(j - i > max){
max = j - i;
}
hash[s.charAt(i)]--;
if(hash[s.charAt(i)] == 0) distinctCount --;
}
return max;
}
}
340. Longest Substring with At Most K Distinct Characters
就像我之前说的，340是Google onsite最喜欢考的一道题，有了前面的铺垫，做起来水到渠成没有任何障碍了。
思想完全一致，代码和上一题完全没有区别，只是把判断条件里面的 count 数字改一下而已。
public class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (s.length() <= k) return s.length();
int j = 0;
int distinctCount = 0;
int[] hash = new int[256];
int max = k;
for (int i = 0; i < s.length(); ++i) {
while (j < s.length()) {
if (hash[s.charAt(j)] == 0 && distinctCount == k) break;
if (hash[s.charAt(j)] == 0) distinctCount++;
hash[s.charAt(j++)]++;
}
if (max < j - i) {
max = j - i;
}
hash[s.charAt(i)]--;
if (hash[s.charAt(i)] == 0) distinctCount--;
}
return max;
}
}
487. Max Consecutive Ones II
论坛答案不是扯淡吗，这题不就是经典前向型指针题微变形吗。
都是新瓶装旧酒。
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int zero = 0;
int j = 0;
int max = 0;
for (int i = 0; i < nums.length; ++i) {
while (j < nums.length && zero <= 1) {
if (nums[j] == 0) {
zero++;
}
j++;
}
if (max < j - i) {
max = zero == 2 ? j - i - 1 : j - i;
}
if (nums[i] == 0) zero--;
}
return max;
}
}
524. Longest Word in Dictionary through Deleting
第一反应：这不还是LC76吗。发现naive了，要求是delete之后，也就是说不能改变顺序。那肯定没办法窗口类指针了。
其实并不难，判断是否为substring（保证顺序）之后，再排序就行，甚至不用priority queue。
public class Solution {
public boolean isSubsequence(String x, String y) {
int j = 0;
for (int i = 0; i < y.length() && j < x.length(); i++)
if (x.charAt(j) == y.charAt(i))
j++;
return j == x.length();
}
public String findLongestWord(String s, List < String > d) {
String max_str = "";
for (String str: d) {
if (isSubsequence(str, s)) {
if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
max_str = str;
}
}
return max_str;
}
}
438. Find All Anagrams in a String
卡了很久，anagram的处理方法和substring的处理方法逻辑上有区别。
要限制j指针，不能跑太快。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s == null || p == null) return result;
int[] target = new int[128];
int[] source = new int[128];
for (int i = 0; i < p.length(); ++i) {
target[p.charAt(i)]++;
}
int j = 0;
for (int i = 0; i < s.length(); ++i) {
while (j < s.length()) {
if (check(source, target)) break;
source[s.charAt(j++)]++;
if (j - i == p.length()) break;
}
if (check(source, target)) {
result.add(i);
}
source[s.charAt(i)]--;
}
return result;
}
private boolean check(int[] a, int[] b) {
for (int i = 0; i < a.length; ++i) {
if (a[i] != b[i]) return false;
}
return true;
}
}
30. Substring with Concatenation of All Words
这个是将word存进window，然后逐词遍历，count--来判断，和前面的window题差不多。就是操作方法麻烦点，每次要取字符串的整个word长度再判断。
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res= new ArrayList<Integer>();
if(s.length()==0||words.length == 0)
return res;
int len=words[0].length();
Map<String, Integer> map= new HashMap<String, Integer>();
for(String w:words)
map.put(w, map.getOrDefault(w, 0)+1);
for(int i=0;i<=s.length()-len*words.length;i++){
Map<String, Integer> map2= new HashMap<String, Integer>(map);
for(int j=0;j<words.length;j++){
String str= s.substring(i+j*len, i+j*len+len);
if(map2.containsKey(str)){
int count=map2.get(str);
if(count==1)
map2.remove(str);
else map2.put(str, map2.get(str)-1);
if(map2.isEmpty()){
res.add(i);
break;
}
}
else break;
}
}
return res;
}