这类题一般给定序列，我们要做的是如何把所有子串都枚举到。
应用双指针算法，需要保证序列的单调性（这里指得不只是单调递增递减，是两个指针向各自原始方向移动，不会退回）
双指针模板：
for (int i = 0, j = 0; i < n; i ++)
while(j < i && check(j, i)) j++;
for (int i = 0, j = len - 1; i < len ; i ++)
while(check2(i, j))j--;
解题思路
当设定[j, i]为不重复子串的时候，序列[j, i]满足单调性（j，i都是单方向执行，不会返回）
这就符合双指针的思想。
再设定一个HashMap，判断序列中是否有重复的字符，如果有，j指针向前，直到[j, i]是不重复子串
每次去一个最大区间长度值。
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
//同向双指针模板
HashMap<Character, Integer> heap = new HashMap<>();
int res = 0;
//对应的就是check（）函数判断的是 ij双指针之间是否有重复字符，如果有，j++
for (int i = 0, j = 0; i < s.length(); i ++)
{
heap.put(s.charAt(i), heap.getOrDefault(s.charAt(i), 0) + 1);
while(heap.get(s.charAt(i)) > 1 && j <= i)
heap.put(s.charAt(j), heap.get(s.charAt(j++)) - 1);
res = Math.max(res, i - j + 1);
}
return res;
}
}
解题思路
在两端设置双指针，由于序列是有序的，两端指针都是不会反向移动
代码
class Solution {
public boolean judgeSquareSum(int c) {
//这道题的数据范围很大2e9，O(N)已经是极限了
int sqrt = (int)Math.sqrt((double)c);
for (int i = 0, j = sqrt; i <= sqrt; i ++)
{
while(i * i + j * j > c && j >= 0) j--;
if ((i * i + j * j) == c) return true;
}
return false;
}
}
解题思路
当ij对应的字符串不相等的时候，就不是回文子串了
这样ij两个指针都是单一方向移动的，符合双指针的思想
那我们如何保证枚举到所有的子串呢? 这就需要我们把中心位置设定在每个点上
每个点也设置为偶数中心点和奇数中心点.....
这样的话，我是可以看到，会有重复遍历的情况，这个算法O(N^2)还是可以改进的。思路
代码
class Solution {
public String longestPalindrome(String s) {
//当ij对应的字符串不相等的时候，就不是回文子串了
//这样ij两个指针都是单一方向移动的，符合双指针的思想
//那我们如何保证枚举到所有的子串呢? 这就需要我们把中心位置设定在每个点上
//每个点也设置为偶数中心点和奇数中心点.....
//这样的话，我是可以看到，会有重复遍历的情况，这个算法还是可以改进的。
int len = s.length();
String ans = new String();
for (int i = 0; i < len; i ++){
int l = i, r = i;
while(l >= 0 && r <= len - 1 && s.charAt(l) == s.charAt(r)){l --; r++;}
if (ans.length() < r - l - 1)
ans = s.substring(l + 1, r);
l = i; r = i + 1;
while(l >= 0 && r <= len - 1 && s.charAt(l) == s.charAt(r)){l --; r++;}
if (ans.length() < r - l - 1)
ans = s.substring(l + 1, r);
}
return ans;
}
}
26. 删除有序数组中的重复项
双指针,当快指针和慢指针指向相同的数，快指针跳过这些数(不做处理)
指向不同的数时，把快指针的数赋值给慢指针的下一位（要么是重复的数，要么就是原数据）
这样慢指针就是符合条件的数组尾指针
class Solution {
public int removeDuplicates(int[] nums) {
//双指针,当快指针和满指针指向不同的数，满指针移动到快指针的地方
//如果指向相同的数，说明这个数要删除
int n = nums.length;
int j = 0;
for (int i = 0; i < nums.length; i ++){
while (j < i && nums[i] != nums[j]) nums[++j] = nums[i];
}
return j + 1;
}
}
class Solution {
public int removeDuplicates(int[] nums) {
//j就是输出数组的尾端点，i是输入数组的尾端点
//把符合条件的都放到慢指针的数组里
//如果nums[j] != nums[i] or nums[i] != nums[j - 1], nums[++j] = nums[i]
int j = 1;
for (int i = 2; i < nums.length; i ++)
{
if (nums[j] != nums[i] || nums[i] != nums[j - 1]) {
nums[++j] = nums[i];
}
}
return j + 1;
}
}
解题思路
快慢指针：fast指针每次移动2步，slow每次移动一步。
这样每次迭代，fast都会比slow多移动一步。
代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//首先我们看到这是单向链表，意味着它只能由一个出口，最多只有一个环
//如果从头节点开始遍历，就意味着一定会进入环
//定义快慢指针（快指针是慢指针的两倍）。如果两个指针相遇，就是有环
//如果快指针走到了尾节点，就说明没有环
ListNode fast = head, slow = head;
if (fast == null || fast.next == null) return false;
while(fast != null){
fast = fast.next; slow = slow.next;
if (fast == null) return false;
fast = fast.next;
if (fast == slow) return true;
}
return false;
}
}
解题思路
//我们让快慢指针的初始位置更改，让他们第一次相遇的位置就是入口点
//位置定在哪里？
//让慢指针从head开始，它进入入口的时候，快指针也进入入口
//快指针初始位置在那？我们先看到：假设快慢指针同时在起点，他们最终相遇的位置距离入口是y
//当慢指针走了x步进入入口，快指针已经在环走了x步。
//慢指针回退y步，快指针回退2y步。慢指针进入入口的时候，快指针在环-y（== x）的地方
//如果快指针从y点（相遇点）出发（它此时距离入口就是环-y == x，和慢指针同样的距离），
//慢指针从head出发，他们最终相遇就是在入口点
代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
//我们让快慢指针的初始位置更改，让他们第一次相遇的位置就是入口点
//位置定在哪里？
//让慢指针从head开始，它进入入口的时候，快指针也进入入口
//快指针初始位置在那？我们先看到：假设快慢指针同时在起点，他们最终相遇的位置距离入口是y
//当慢指针走了x步进入入口，快指针已经在环走了x步。
//慢指针回退y步，快指针回退2y步。慢指针进入入口的时候，快指针在环-y（== x）的地方
//如果快指针从y点（相遇点）出发（它此时距离入口就是环-y == x，和慢指针同样的距离），
//慢指针从head出发，他们最终相遇就是在入口点
ListNode fast = head, slow = head;
while(fast != null){
fast = fast.next; slow = slow.next;
if (fast == null) return null;
fast = fast.next;
if (fast == slow){
//System.out.println(slow.val);
slow = head;
while(fast != slow){
fast = fast.next; slow = slow.next;
}
return slow;
}
}
return null;
}
}
解题思路
把下标看成一个点，值作为下一个连接点。
除去起始点0，剩下的n-1个点都有一条出边（其中一个点有两条入边），意味着有一个环。
相当于找环的入口点。
那么就类似于LC142题。找到两个点的相遇点作为快指针的起点。
当快慢指针相遇的时候就是入口点。
代码
class Solution {
public int findDuplicate(int[] nums) {
//一定会存在环
int i = 0, j = 0;
while(true){
i = nums[i]; j = nums[j];
i = nums[i];
if (i == j) break;
}
j = 0;
while(i != j){
i = nums[i]; j = nums[j];
}
return i;
}
}
滑动窗口（单调队列）：
单调队列的性质就是任何一个数不会重复地添加到队列中，并且相对与队列中的元素来说，新进队列的元素总是更加具有竞争力的（生存周期更长）。
因此单调队列解决题目的关键在于如何设定进队出队的条件。
if (hh <= tt && check1(i, hh))hh++;
while(hh <= tt && check2(i, tt)) tt--;
q[++tt] = i;
