1, 双指针滑动窗口问题，一般情况下都是先动后面的指针，而且一般都是计数问题，那么就先把后面指针挪动一个，进行相应的操作，然后再判断前一个指针的条件
证明双指针的时候，多数都是设置i为能满足条件的终点，j是能满足条件的前一个指针能到达的最远的值，然后去证明
同一个字符串的同相双指针：
1: 设置i, j都为0, 设置计数的map
2. i每次走一次，并处理i这个指针对应的该处理的逻辑操作
3. while循环走j，查看新加的这个i指针指的元素会不会对逻辑产生影响，导致条件不满足，如果使得条件不满足了，那么就一直走j（j++，直到再次满足条件就停止走j
4. 此时得到一个合法解，再做一些相应的比较
Leetcode 3
典型的同向双指针
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
//计数map
Map<Character, Integer> map = new HashMap<>();
//设置双指针
for(int i = 0, j = 0; i < s.length(); i++){
char c = s.charAt(i);
//无论怎样都走i
map.put(c, map.getOrDefault(c, 0) + 1);
//挪动j，保证i新指向的元素不影响要满足的逻辑
while(j < s.length() && map.get(c) > 1){
map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
j++;
}
//找到一个合法解，然后进行相应比较的逻辑
res = Math.max(res, i - j + 1);
}
return res;
}
}
两个字符串的双指针
两个字符串匹配的双指针做法，首先需要一个need map来计数用来匹配的短字符
还需要一个计数cnt，来计数已经满足条件的字符的个数
然后在匹配过程，可以省去一个记录滑动窗口字符统计的map，可以直接在need map上做计算
找substring的while循环走j的条件一般就是i - j + 1 > t.length()，
这里为什么用equals 而不用== Integer能用==的范围是 -128 - 127
http://www.51gjie.com/java/592.html
Leetcode 567. Permutation in String
同样的模板
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> need = new HashMap<>();
for(int i = 0; i < s1.length(); i++){
char c = s1.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int n = s2.length();
int cnt = 0;
for(int i = 0, j = 0; i < n; i++){
char c = s2.charAt(i);
//无论怎样都走i
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))) cnt++;
////挪动j，保证i新指向的元素不影响要满足的逻辑
//也就是左侧窗口的是否要收缩
while(i - j + 1> s1.length()){
char d = s2.charAt(j);
//只有第一次变成不等于的时候cnt--
if(need.containsKey(d) && window.get(d) == need.get(d)){
cnt--;
}
window.put(d, window.get(d) - 1);
// if(need.containsKey(d) && window.get(d) < need.get(d)){
// cnt--;
// }
j++;
}
//判断是否满足题中条件
if(cnt == need.size()) return true;
}
return false;
}
}
用一个map的方法，可以避免需要Integer.equals()
class Solution {
public boolean checkInclusion(String t, String s) {
Map<Character, Integer> need = new HashMap<>();
for(int i = 0; i < t.length(); i++){
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
for(int i = 0, j = 0, cnt = 0; i < s.length(); i++){
char c = s.charAt(i);
if(need.containsKey(c)){
need.put(c, need.get(c)-1);
if(need.get(c) == 0) cnt++;
}
while(i - j + 1 > t.length()){
char d = s.charAt(j);
if(need.containsKey(d)){
if(need.get(d) == 0) cnt--;
need.put(d, need.get(d) + 1);
}
j++;
}
if(cnt == need.keySet().size()) return true;
}
return false;
}
}
Leetcode 438. Find All Anagrams in a String
同样模板
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character, Integer> need = new HashMap<>();
for(int i = 0; i < p.length(); i++){
char c = p.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
List<Integer> ans = new ArrayList<>();
Map<Character, Integer> window = new HashMap<>();
int cnt = 0;
int n = s.length();
for(int l = 0, r = 0; r < n; r++){
char c = s.charAt(r);
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))) cnt++;
while(r - l + 1 > p.length()){
char d = s.charAt(l);
if(need.containsKey(d) && window.get(d).equals(need.get(d))){
cnt--;
}
window.put(d, window.get(d) - 1);
l++;
}
if(cnt == need.size()){
ans.add(l);
}
}
return ans;
}
}
Leetcode 76. Minimum Window Substring
也可以用相同的模板
1.先统计要找的字符串的各个字符的数量
2.双指针走(秉承一个理念，就是i走，j走， j能怎么走用一个while循环，什么情况下 j是仅仅 < i就可以还是i和j要满足一个条件，类似于上面两道题的i - j + 1 > t.lenght() j可以走)然后在窗口内部做一个数据计算。 别忘记要设置一个cnt来计算有效字符，能满足条件的字符
3.根据题要的条件是最大值还是最小值还是最小字符串
相同的模板
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for(int i = 0; i < t.length(); i++){
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
String res = "";
int len = Integer.MAX_VALUE;
int cnt = 0;
Map<Character, Integer> window = new HashMap<>();
for(int i = 0, j = 0; i < s.length(); i++){
char c = s.charAt(i);
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c).equals(need.get(c))) cnt++;
while(j < i && (!need.containsKey(s.charAt(j)) || window.get(s.charAt(j)) > need.get(s.charAt(j)) ) ) {
window.put(s.charAt(j), window.get(s.charAt(j)) - 1);
j++;
}
//并不能保证拿到的cnt一定是合法的
if(cnt == need.keySet().size() && i - j + 1 < len){
len = i - j + 1;
res = s.substring(j, i + 1);
}
}
return res;
}
}
https://www.acwing.com/problem/content/description/801/
最长不连续子串，也是这样的模板
1.不是两个字符串比较，那么就不需要need map，只需要一个map去当滑动窗口的map计数
2.i指针，不论什么情况，先加入进窗口
3.j指针收缩窗口的条件， 这里是只要i指着的元素超过一个，那么就肯定不行
4.根据条件进行判断，取最大或者最小值
原地法修改数组， 使用双指针
1.这种双指针就是后面的双指针在后面代表下一次要插入的数的index，前面的双指针是走的快的，去做逻辑比较的
Leetcode 26. Remove Duplicates from Sorted Array
这样思考，如果正常copy数组就是
for(int i = 0; i < nums.length; i++){
nums[j++] = nums[i];
}
这里就要考虑的是，限制条件了，那么什么条件下可以copy这个数字呢， 第一种是开头元素i == 0, 第二种就是这个数字不是重复的数字
for(int i = 0; i < nums.length; i++){
if(i == 0 || nums[i] != nums[i - 1]){
nums[j] = nums[i];
j++;
}
}
Leetcode 83. Remove Duplicates from Sorted List
链表的双指针，因为链表不能往前找，所以只能看和后面的是否一样，
链表也是，如果正常copy一个链表
链表不能往回比较，只能往下一个比较，这样没法判断这个node是否是重复的node，因为这个node没法跟自己比较，这里的p就相当于当前不重复的node的最后一个，要找到与这个node不一样的,如果qNode和p一样，那么q就要往后走，直到找到不一样的，把p连向q
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
//当前最后一个不一样的node
ListNode p = head;
ListNode q = head;
while(p != null){
while(q != null && q.val == p.val){
q = q.next;
}
p.next = q;
p = p.next;
}
return head;
}
}
回文串问题
回文串问题，就是中间往两边扩散
单调队列，滑动窗口
使用deque实现
Deque[HTML_REMOVED] q = new ArrayDeque<>();
为什么这种滑动窗口内求最值，不能用map解决，Map维护一个滑动窗口，还要去维护最值，如果用treeMap维护最值的话，时间复杂度是logN，而deque可以做到O(1)的时间复杂度来解决这个问题，相当于deque就是一个滑动的窗口在数组上走，对于超出滑动窗口边界的元素要在队头出队，肯定是队头，因为往后滑动嘛，然后新进来的元素，如果比队尾大，那么队尾也出队，如果新进来的数大，那比他小的数一定不需要用到了。
for(int i = 0, idx = 0; i < n; i++){
if(!q.isEmpty() && i - k + 1 > q.peekFirst()) q.removeFirst();
while(!q.isEmpty() && nums[i] > nums[q.peekLast()]) q.removeLast();
q.addLast(i);
if(i >= k - 1) res[idx++] = nums[q.peekFirst()];
}
其实也是前文所说的那种思想，不论新进来的数怎样，他都入队，只是去考虑队中的元素，哪些需要出队就好了，就像双指针滑动窗口，不论怎样i指针指向的元素都如window窗口，再根据逻辑判断j指针指的元素，然后再判断最值或者一些限定条件
