滑动窗口 双指针（双指针和滑动窗口区别）

双指针的算法原理，通过两个指针在一个for循环下完成两个for循环的工作。时间复杂度从优化到了。

双指针的算法模板比较简单，突破口主要是需要找到题目中的单调性，从而加以利用。

快慢指针

快慢指针一个链表操作技巧，它还有一个有趣的名字，龟兔赛跑。

• 移除元素：

1. classSolution{
2. public:
3. intremoveElement(vector<int>&nums,intval){
4. intslowIndex=0;
5. for(intfastIndex=0;fastIndex<nums.size();fastIndex++){
6. if(val!=nums[fastIndex]){
7. nums[slowIndex++]=nums[fastIndex];
8. }
9. }
10. returnslowIndex;
11. }
12. };

• 环的入口位置：应用快慢指针，快指针走两步，慢指针走一步。假使有环，两指针迟早相遇;假使无环，快指针就会走到尽头，退出循环。如果有环，慢指针重新开始，此时快指针是交点，同速两指针交点必是入口。

1. classSolution{
2. public:
3. ListNode*detectCycle(ListNode*head){
4. ListNode*slow=head;
5. ListNode*fast=head;
6. while(fast&&fast->next){
7. fast=fast->next->next;
8. slow=slow->next;
9. if(fast==slow)break;
10. }
12. if(fast&&fast->next){
13. slow=head;
14. while(slow!=fast){
15. slow=slow->next;
16. fast=fast->next;
17. }
18. returnslow;
19. }
20. returnnullptr;
21. }
22. };

• 链表的中间结点：应用快慢指针，快指针走两步，慢指针走一步。快指针走到尽头时，慢指针刚好走了一半，返回即为中间结点。
• 删除链表的倒数第 N 个结点：快指针先走 n 步，然后快慢指针同时走，快指针走到头时，慢指针就在倒数第 n 个位置。

反向指针

反向指针经典题目是N sum 系列和二分变种题目。

N sum 系列的经典题目是：三数之和

1. defthreeSum(nums):
2. nums.sort()
3. #[-4,-1,-1,0,1,2]
4. res_list=[]
5. #头部循环查找
6. foriinrange(len(nums)):
7. #必须判断nums[i]>nums[i-1]这个条件
8. ifi==0ornums[i]>nums[i-1]:
9. #最左端
10. l=i+1
11. #最右端
12. r=len(nums)-1
13. whilel<r:#正在查找
14. three_sum=nums[i]+nums[l]+nums[r]
15. ifthree_sum==0:
16. res_list.append([nums[i],nums[l],nums[r]])
17. l+=1#右移一位
18. r-=1#左移一位
19. whilel<randnums[l]==nums[l-1]:
20. #从左往右，相同数值直接跳过
21. l+=1
22. whiler>landnums[r]==nums[r+1]:
23. #从右往左，相同数值直接跳过
24. r-=1
25. elifthree_sum>0:
26. #大于零，右边数值大，左移
27. r-=1
28. else:
29. #小于零，左边数值小，右移
30. l+=1
31. returnres_list

在四种二分变种中，根据王争算法专栏中，写死low = 0，high = len(list) - 1。循环条件low <= high。往左移动high = mid - 1，往右移动low = mid + 1

1. defbinary_search(nums,target):
2. '''标准二分算法模板'''
3. low=0
4. high=len(nums)-1#注意1low和high用于跟踪在其中查找的列表部分
5. whilelow<=high:#注意2只要还没有缩小到只有一个元素，就不停的检查
6. mid=(low+high)//2
7. iflist[mid]==target:
8. returnmid
9. eliflist[mid]>target:
10. high=mid-1#注意3猜的数字大了
11. eliflist[mid]<target:
12. low=mid+1#注意4猜的数字小了
13. returnmid
16. defbsearch_low(nums,target):
17. '''求第一个等于定值'''
18. low=0
19. high=len(nums)-1
20. #这里需要<=
21. whilelow<=high:
22. #这里需要注意：就是使用((high-low)>>1)需要双扩号
23. mid=low+((high-low)>>1)
24. ifnums[mid]<target:
25. low=mid+1
26. elifnums[mid]>target:
27. high=mid-1
28. else:
29. ifmid==0ornums[mid-1]!=target:
30. returnmid
31. else:
32. high=mid-1
34. return-1
36. defbsearch_high(nums,target):
37. '''求最后一个等于定值的'''
38. low=0
39. higt=len(nums)-1
40. whilelow<=higt:
41. mid=low+((higt-low)>>1)
42. ifnums[mid]>target:
43. higt=mid-1
44. elifnums[mid]<target:
45. low=mid+1
46. else:
47. ifmid==(len(nums)-1)ornums[mid]!=nums[mid+1]:
48. returnmid
49. else:
50. low=mid+1
51. return-1
53. '''
54. 查找第一个大于等于给定值的元素
55. *如序列：3，4，6，7，19查找第一个大于5的元素，即为6，return2
56. *第一个大于给定值，则说明上一个小于给定值，依次判断
57. '''
58. defbsearch_low_not_less(nums,target):
59. low=0
60. high=len(nums)-1
61. while(low<=high):
62. mid=low+((high-low)>>1)
63. ifnums[mid]>=target:
64. ifmid==0ornums[mid-1]<target:
65. returnmid
66. else:
67. #往左移动
68. high=mid-1
69. else:
70. #往右移动
71. low=mid+1
72. return-1
74. '''
75. 查找第一个小于给定值的元素
76. *如序列：3，4，6，7，19查找第一个小于5的元素，即为4，返回1
77. *第一个大于给定值，则说明上一个小于给定值，依次判断
78. '''
79. defbsearch_high_not_greater(nums,target):
80. '''求最后一个小于等于值'''
81. low=0
82. higt=len(nums)-1
83. whilelow<=higt:
84. mid=low+((higt-low)>>1)
85. ifnums[mid]<=target:
86. if(mid==len(nums)-1)or(nums[mid+1]>target):
87. returnmid
88. else:
89. low=mid+1
90. else:
91. higt=mid-1
92. return-1

滑动窗口

原文：https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA

滑动窗口算法是双指针技巧的最高境界，主要用于两个字符串匹配的问题。

掌握了滑动窗口的解题模板可以轻松解决一系列字符串匹配的问题。

下面模板代码来源labuladong，解决LeetCode 76 题，Minimum Window Substring，求最小覆盖子串。

1. /*滑动窗口算法框架*/
2. stringminWindow(strings,stringt){
3. //两个unordered_map，一个need记录模式串的字符数量，一个window记录窗口的字符
4. unordered_map<char,int>need,window;
5. //初始化need
6. for(charc:t)need[c]++;
8. intleft=0,right=0;
9. //两个unordered_map的符合条件数目
10. intvalid=0;
11. //记录最小覆盖子串的起始索引及长度
12. intstart=0,len=INT_MAX;
13. while(right<s.size()){
14. //c是将移入窗口的字符
15. charc=s[right];
16. //右移窗口
17. right++;
18. //进行窗口内数据的一系列更新
19. if(need.count(c)){
20. window[c]++;
21. if(window[c]==need[c])
22. valid++;
23. }
25. //判断左侧窗口是否要收缩
26. while(valid==need.size()){
27. //在这里更新最小覆盖子串
28. if(right-left<len){
29. start=left;
30. len=right-left;
31. }
32. //d是将移出窗口的字符
33. chard=s[left];
34. //左移窗口
35. left++;
36. //进行窗口内数据的一系列更新
37. if(need.count(d)){
38. if(window[d]==need[d])
39. valid--;
40. window[d]--;
41. }
42. }
43. }
44. //返回最小覆盖子串
45. returnlen==INT_MAX?
46. "":s.substr(start,len);
47. }

在python里unodered map可以用collections.defaultdict和collections.Counter实现

原文链接：https://mp.weixin.qq.com/s/U-lUGtVkLR9i0M4MdwjInQ

如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）

您的姓名 *

身份证号码 *

手机号码 *

选择地区 *

详细地址 *

留言备注 *