6/14, Two Pointers, 双指针，窗口类
Minimum Size Subarray Sum
这种看起来有点 greedy 味道的双指针都不同程度上利用后面状态的增长性质，直接排除一些元素，减少搜索范围。
在这道题里，如果 [i - j] 的 subarray 已经 >= target 了，考虑任何 j 以后的元素都是没有意义的，因为数组都是正数，依然会 >= target，长度还一定比当前的长。
当sum大于等于target的时候, 用while loop来增加left指针, 因为有可能rightmost新添加了一个数100, 而left指针连续指了1, 1, 1, 这样的数字, 还有减少length的空间.
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left = 0; int sum = 0;int minLen = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
sum += nums[i];
while(sum>=s){
minLen = Math.min(i-left+1, minLen);
sum-=nums[left];
left++;
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
}
Maximum Size Subarray Sum Equals k
这题的做法其实和上一题没啥关系，也不属于这个分类。。不过看在长得非常像的份上就一起写了吧 = =
这道题允许有负数的存在, 这样就不能用sliding window, sliding window在增加的时候是保证单调性的, 当sum>target的时候可以停止移动right指针.
这题其实是 prefix sum array + two sum，利用前缀和数组实现快速区间和查询，同时 two sum 的方法快速地位 index.
这种 prefix sum 的下标要格外小心，很容易标错。。target value 差也是，写之前多手动过几个 case 保平安。
public int maxSubArrayLen(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int sum = 0;map.put(0,-1);
int result = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
if(map.containsKey(sum-k)){
result = Math.max(result, i-map.get(sum-k));
}
if(!map.containsKey(sum))
map.put(sum, i);
}
return result;
}
Longest Substring Without Repeating Characters
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null || s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int left = 0;int ans = Integer.MIN_VALUE;int count = 0;
int i=0;
for(;i<s.length();i++){
char ch = s.charAt(i);
if(!map.containsKey(ch)){
map.put(ch,1);
}
else{
ans = Math.max(ans, i-left);
while(map.containsKey(ch)){
map.remove(s.charAt(left));
left++;
}
map.put(ch,1);
}
}
return Math.max(ans, i-left);
}
}
以下代码值得借鉴的地方, 因为一共char 256个字符, 所以建立boolean[256] 数组够用, left指针i可以通过外层循环loop来递增, 这个trick目前掌握的还不太好, 慎用.
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() <= 1) return s.length();
int max = 1;
boolean[] hash = new boolean[256];
int j = 0;
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;
}
}
Minimum Window Substring
对 Target string 做预处理，返回 int[] hash 和需要 match 的字符串数量；
count 记录有效字符数, 当有效字符数等于target.length的时候
移动左指针直到不能移动(移动条件: 当前字符不属于target, 或当前字符数量大于target).
计算min length
public class Solution {
public String minWindow(String s, String t) {
if(t.length()>s.length()) return "";
HashMap<Character, Integer> target = new HashMap<Character, Integer>();
for(int i=0;i<t.length();i++){
char c = t.charAt(i);
target.put(c, target.getOrDefault(c,0)+1);
}
int count = 0; int left =0 ; int start =0;int end =0; int min = Integer.MAX_VALUE;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(target.containsKey(c)){
if(!map.containsKey(c) || map.get(c)<target.get(c))
count++;
map.put(c, map.getOrDefault(c,0)+1);
}
if(count==t.length()){
char tmp = s.charAt(left);
while(!map.containsKey(tmp)||map.get(tmp)>target.get(tmp)){
if(map.containsKey(tmp))
map.put(tmp, map.get(tmp)-1);
left++;
tmp = s.charAt(left);
}
if(i-left+1<min){
min = i-left+1;
start = left;
end = i;
}
}
}
return min==Integer.MAX_VALUE? "" : s.substring(start, end+1);
}
}
6/15, Two Pointers, 双指针，窗口类
这两题有一个 trick 和 Minimum Window Substring 非常像，就是维护一个 "curCount" 代表目前 (i,j) 之间 match 上的数量，而通过 hash[] 的正负充当计数器的作用。
Longest Substring with At Most Two Distinct Characters
Longest Substring with At Most K Distinct Characters
public class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
if(s==null || s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int left = 0;int k = 2;int ans = Integer.MIN_VALUE;int count = 0;
int i=0;
for(;i<s.length();i++){
char ch = s.charAt(i);
if(map.containsKey(ch)){
map.put(ch, map.get(ch)+1);
}
else{
map.put(ch,1);
count++;
}
if(count>k){
ans = Math.max(ans, i-left);
while(count>k){
if(map.get(s.charAt(left))==1){
map.remove(s.charAt(left));
count--;
}
else
map.put(s.charAt(left),map.get(s.charAt(left))-1);
left++;
}
}
}
return Math.max(ans, i-left);
}
}
Smallest Range
Square Onsite第二轮题，面试官给了一个Google Search Webpage，对关键词搜索的例子。顺着当时的思路撸了一个。先选一组，再move min，试图缩小range，81/86后TLE。面试时Square喜欢当场出正确结果，而对复杂度没那么关心的时候，我选择了简单 快速 直接。面试官问能否优化的时候，我说priority queue，居然被否定了。论坛里最后的高票答案就是pq每次抽取最小min tuple，加入新min tuple，max在每次加入新tuple的时候可以维护。
public int[] smallestRange(int[][] nums) {
PriorityQueue<Element> pq = new PriorityQueue<Element>(new Comparator<Element>() {
public int compare(Element a, Element b) {
return a.val - b.val;
}
});
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
Element e = new Element(i, 0, nums[i][0]);
pq.offer(e);
max = Math.max(max, nums[i][0]);
}
int range = Integer.MAX_VALUE;
int start = -1, end = -1;
while (pq.size() == nums.length) {
Element curr = pq.poll();
if (max - curr.val < range) {
range = max - curr.val;
start = curr.val;
end = max;
}
if (curr.idx + 1 < nums[curr.row].length) {
curr.idx = curr.idx + 1;
curr.val = nums[curr.row][curr.idx];
pq.offer(curr);
if (curr.val > max) {
max = curr.val;
}
}
}
return new int[] { start, end };
}
class Element {
int val;
int idx;
int row;
public Element(int r, int i, int v) {
val = v;
idx = i;
row = r;
}
}
public class Solution {
class Tuple{
int idx1;
int idx2;
int val;
public Tuple(int idx1, int idx2, int val){
this.idx1 = idx1;
this.idx2 = idx2;
this.val = val;
}
}
public Tuple getMin(List<Tuple> list){
int curMin = Integer.MAX_VALUE; Tuple min = null;
for(Tuple t : list)
if(t.val<curMin){
min = t; curMin = t.val;
}
return min;
}
public Tuple getMax(List<Tuple> list){
int curMax = Integer.MIN_VALUE; Tuple max = null;
for(Tuple t : list)
if(t.val>curMax){
max = t; curMax = t.val;
}
return max;
}
public int[] smallestRange(List<List<Integer>> nums) {
ArrayList<Tuple> list = new ArrayList<Tuple>(); int idx = 0;
for(List<Integer> l : nums){
list.add(new Tuple(idx++, 0, l.get(0)));
}
int diff = Integer.MAX_VALUE; int[] ans = new int[2];
while(true){
Tuple min = getMin(list);
Tuple max = getMax(list);
//System.out.println("min: " + min.val + " max: " + max.val);
if(max.val-min.val<diff){
ans[0] = min.val; ans[1] = max.val; diff = max.val-min.val;
}
list.remove(min);
if(min.idx2 == nums.get(min.idx1).size()-1) break;
list.add(new Tuple(min.idx1, min.idx2+1, nums.get(min.idx1).get(min.idx2+1)));
min = getMin(list);
}
return ans;
}
}
Max Consecutive Ones II
最简单的方式是存一个prevCount的变量，O(1) space, 每次碰到0的时候，遇到1的数量是prevCount＋Count＋1，如果0后面跟的是1的话，prevCount＝count， 否则prevCount＝0.
注意两个corner case，[1,1,1,1] ，一个0都没有出现，ans是count的值。
最后一个是1，循环完以后要补一个判断。不要忽视很多循环都最后要判断一下，
public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int prevCount = 0; int count = 0; int ans = 0; boolean zero = false;
for(int i=0;i<nums.length;i++){
if(nums[i]==1) count++;
else{
ans = Math.max(ans, prevCount+count+1);
if(i+1>=nums.length||nums[i+1]==1) prevCount = count;
else prevCount = 0;
count=0;
zero = true;
}
}
if(zero) ans = Math.max(ans, prevCount+count+1);
else ans = Math.max(ans, count);
return ans;
}
}
简洁解法是two pointers(sliding window)的解法。这个同时可以扩展到k个0的情况。然而这个需要保存部分input，没法拓展到stream的情况
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, zero = 0, k = 1; // flip at most k zero
for (int l = 0, h = 0; h < nums.length; h++) {
if (nums[h] == 0)
zero++;
while (zero > k)
if (nums[l++] == 0)
zero--;
max = Math.max(max, h - l + 1);
}
return max;
}
stream 的情况下，不需要保存input，只需要记录0的index出现的位置。
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, k = 1; // flip at most k zero
Queue<Integer> zeroIndex = new LinkedList<>();
for (int l = 0, h = 0; h < nums.length; h++) {
if (nums[h] == 0)
zeroIndex.offer(h);
if (zeroIndex.size() > k)
l = zeroIndex.poll() + 1;
max = Math.max(max, h - l + 1);
}
return max;
}