IDEA激活码目录
双指针
双指针比较灵活，可以大大降低时间复杂度，可用在数组，单链表等数据结构中。
快慢指针：一快一慢，步长一大一小。例如，是否有环问题（看慢指针是否能追上快指针），单链表找中间节点问题（快指针到单链表结尾，慢指针到一半）。
对撞指针：一左一右向中间逼近。
滑动窗口：类似计算机网络中的滑动窗口，一般是右端向右扩充，达到停止条件后右端不动，左端向右端逼近，逼近达到停止条件后，左端不动，右端继续扩充。
快慢指针
例题
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
思路
设置一快一慢指针，如果快指针追上慢指针，则有环。如果快指针到达链表尾，说明无环。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr||head->next==nullptr)return false;
ListNode * slow = head;
ListNode * fast = slow->next;
while(fast!=slow)
{
if(fast==nullptr||fast->next==nullptr)return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};对撞指针
例题
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1：
输入："hello"
输出："holle"
示例 2：
输入："leetcode"
输出："leotcede"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string
思路
设置左右两个指针，从两侧指向元音字母，不相等时交换。如果两指针相撞（左右指针指向同一位置或左指针在右指针右侧），则停止。
代码
class Solution {
public:
string yuan = "aeiouAEIOU";
bool isYuan(char c)
{
for(auto a:yuan)
{
if(c==a)return true;
}
return false;
}
string reverseVowels(string s) {
int n = s.length();
if(n==0)return s;
int left = 0;
int right = n-1;
while(left<right)
{
if(!isYuan(s[left])){left++;continue;};
if(!isYuan(s[right])){right--;continue;};
if(s[left]!=s[right])swap(s[left++],s[right--]);
else
{
left++;
right--;
}
}
return s;
}
};滑动窗口
滑动窗口：有左右端点和长度，根据题目调整左右端点的位置进行滑动，也是一种特殊的双指针。
例题
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
思路
窗口右端点向右扩展，停止条件：有了一个重复的字符或到达最后。右端点停止后，左端点收缩，停止条件：重复的字符不在滑动窗口内。
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
if(n==0) return 0;
int left = 0;
unordered_set<char> sub;
int cnt = 0;
for(int right=0;right<n;++right)
{
if(sub.find(s[right])==sub.end()) sub.insert(s[right]);
else
{
cnt = cnt>sub.size()?cnt:sub.size();
while(sub.find(s[right])!=sub.end())
{
sub.erase(s[left]);
++left;
}
sub.insert(s[right]);
}
}
cnt = cnt>n-left?cnt:n-left;
return cnt;
}
};查找可以使用unorded_map更快。
示意图如上，当然，代码是先去掉重复的，例如abc，a即将重复，先去除左边，直到去除了a，再添加a
