双指针和滑动窗口算法模板

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

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

快慢指针

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

移除元素： class Solution {  public:     int removeElement(vector<int>& nums,模板 int val) {          int slowIndex = 0;         for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {              if (val != nums[fastIndex]) {                  nums[slowIndex++] = nums[fastIndex];             }         }         return slowIndex;     } };  环的入口位置：应用快慢指针，快指针走两步，双指算法慢指针走一步。针和假使有环，滑动两指针迟早相遇;假使无环，窗口快指针就会走到尽头，模板退出循环。如果有环，慢指针重新开始，此时快指针是交点，同速两指针交点必是入口。 class Solution {  public:     ListNode *detectCycle(ListNode *head) {          ListNode* slow = head;         ListNode* fast = head;         while (fast && fast->next){              fast = fast->next->next;             slow = slow->next;             if (fast == slow) break;         }         if (fast && fast->next){              slow = head;             while(slow!=fast){                  slow = slow->next;                 fast = fast->next;             }             return slow;         }         return nullptr;     } };  链表的中间结点：应用快慢指针，快指针走两步，慢指针走一步。快指针走到尽头时，网站模板慢指针刚好走了一半，返回即为中间结点。 删除链表的倒数第 N 个结点：快指针先走 n 步，然后快慢指针同时走，快指针走到头时，慢指针就在倒数第 n 个位置。

反向指针

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

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

def threeSum(nums):     nums.sort()     # [-4, -1, -1, 0, 1, 2]     res_list = []     # 头部循环查找     for i in range(len(nums)):      #  必须判断 nums[i] > nums[i - 1]这个条件         if i == 0 or nums[i] > nums[i - 1]:             # 最左端             l = i + 1             # 最右端             r = len(nums) - 1             while l < r:  # 正在查找                 three_sum = nums[i] + nums[l] + nums[r]                 if three_sum == 0:                     res_list.append([nums[i], nums[l], nums[r]])                     l += 1  # 右移一位                     r -= 1  # 左移一位                     while l < r and nums[l] == nums[l - 1]:                         # 从左往右，相同数值直接跳过                         l += 1                     while r > l and nums[r] == nums[r + 1]:                         # 从右往左，相同数值直接跳过                         r -= 1                 elif three_sum > 0:                     # 大于零，右边数值大，左移                     r -= 1                 else:                     # 小于零，左边数值小，右移                     l += 1     return res_list 

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

def binary_search(nums, target):  标准二分算法模板     low = 0     high = len(nums) - 1  # 注意1 low和high用于跟踪在其中查找的列表部分     while low <= high:  # 注意2 只要还没有缩小到只有一个元素，就不停的检查         mid = (low + high) // 2         if list[mid] == target:             return mid         elif list[mid] > target:             high = mid - 1  # 注意3 猜的数字大了         elif list[mid] < target:             low = mid + 1   # 注意4 猜的数字小了     return mid def bsearch_low(nums,target):     求第一个等于定值      low = 0     high = len(nums) - 1     # 这里需要 <=     while low <= high:         # 这里需要注意： 就是使用((high - low) >> 1)需要双扩号         mid = low + ((high - low) >> 1)         if nums[mid] < target:             low = mid + 1         elif nums[mid] > target:             high = mid - 1         else:             if mid == 0 or nums[mid-1] != target:                 return mid             else:                 high = mid -1     return -1 def bsearch_high(nums,target):     求最后一个等于定值的     low = 0     higt = len(nums) -1     while low <= higt:         mid = low + ((higt- low) >>1 )         if nums[mid] > target:             higt = mid - 1         elif nums[mid] < target:             low = mid +1         else:             if mid == (len(nums) -1) or nums[mid] != nums[mid+1]:                 return mid             else:                 low = mid +1     return  -1 查找第一个大于等于给定值的元素 * 如序列：3，4，云服务器6，7，19 查找第一个大于5的元素，即为6，return 2 * 第一个大于给定值，则说明上一个小于给定值，依次判断 def bsearch_low_not_less(nums,target):     low = 0     high = len(nums) -1     while(low<=high):         mid = low + ((high-low) >>1)         if nums[mid] >= target:             if mid == 0 or nums[mid - 1] < target:                 return mid             else:                 # 往左移动                 high = mid - 1         else:             # 往右移动             low = mid +1     return -1 查找第一个小于给定值的元素 * 如序列：3，4，6，7，19 查找第一个小于5的元素，即为4，返回1 * 第一个大于给定值，则说明上一个小于给定值，依次判断 def bsearch_high_not_greater(nums,target):     求最后一个小于等于值     low = 0     higt = len(nums) -1     while low <= higt:         mid = low + (( higt -low ) >> 1)         if nums[mid] <= target:             if (mid == len(nums) -1) or (nums[mid + 1] > target):                 return mid             else:                 low = mid +1         else:             higt = mid -1     return  -1 

滑动窗口

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

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

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

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

/* 滑动窗口算法框架 */ string minWindow(string s, string t) {       // 两个unordered_map ，一个need记录模式串的字符数量，一个window记录窗口的云南idc服务商字符     unordered_map<char, int> need, window;     // 初始化need     for (char c : t) need[c]++;     int left = 0, right = 0;     // 两个unordered_map的符合条件数目     int valid = 0;     // 记录最小覆盖子串的起始索引及长度     int start = 0, len = INT_MAX;     while (right < s.size()) {          // c 是将移入窗口的字符         char c = s[right];         // 右移窗口         right++;         // 进行窗口内数据的一系列更新         if (need.count(c)) {              window[c]++;             if (window[c] == need[c])                 valid++;         }         // 判断左侧窗口是否要收缩         while (valid == need.size()) {              // 在这里更新最小覆盖子串             if (right - left < len) {                  start = left;                 len = right - left;             }             // d 是将移出窗口的字符             char d = s[left];             // 左移窗口             left++;             // 进行窗口内数据的一系列更新             if (need.count(d)) {                  if (window[d] == need[d])                     valid--;                 window[d]--;             }                             }     }     // 返回最小覆盖子串     return len == INT_MAX ?         "" : s.substr(start, len); } 

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

很赞哦!（89）