算法思想中的两点法和滑动窗口法及python实例

浅浅的花香味﹌ 2022-03-10 08:58 210阅读 0赞

两点法（Two Pointer Approach），也就是双指针法，它一般可以把复杂度从穷举法的O(n^2)减小到O(n)

两点法非常有用，很多问题都可以用，如快慢指针，还有求排序数组中的两数和问题

两点法对应了两个指针，左右指针之间也就是一个窗口，当左右指针变化时，也就对应着窗口的滑动。所以实际上滑动窗口法是属于两点法的。

滑动窗口法（Sliding Window）一般是通过左右指针的变化使窗口一直向右滑，同时检测窗口内元素是否满足要求，而两点法的使用相对是更广泛的，是针对两个不同指针的操作，如快慢指针并不能算作滑动窗口法，但也是两点法的应用。

#### **python实例1：** ####

**Minimum Size Subarray Sum (leetcode 209)**

Given an array of **n** positive integers and a positive integer **s**, find the minimal length of a **contiguous** subarray of which the sum ≥ **s**. If there isn’t one, return 0 instead.

**Example:**

Input: s = 7, nums = [2,3,1,2,4,3]
    Output: 2
    Explanation: the subarray [4,3] has the minimal length under the problem constraint.

class Solution(object):
        def minSubArrayLen(self, s, nums):
            minlen = float('inf')
            left, right= 0, 0
            while right<len(nums):
                num_sum = sum(nums[left:(right+1)])
                if num_sum>=s:
                    minlen=min(minlen,right+1-left)
                    left+=1
                else:
                    right+=1
            return 0 if minlen==float('inf') else minlen

上述代码是典型的两点法的写法，包括left, right两个指针，但求和部分可以优化，因为有很大部分求和重复在做，优化如下

class Solution(object):
        def minSubArrayLen(self, s, nums):
            minlen = float('inf')
            left, num_sum= 0, 0
            for i in range(len(nums)):
                num_sum += nums[i]
                while num_sum>=s:
                    minlen=min(minlen,i+1-left)
                    num_sum -= nums[left]
                    left+=1
            return 0 if minlen==float('inf') else minlen

优化后求和的每一步只需要加减一个数，之前的right 变成了循环中的 i 变量。

#### **python实例2：** ####

**Minimum Window Substring (leetcode 76)**

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

**Example:**

Input: S = "ADOBECODEBANC", T = "ABC"
    Output: "BANC"

这道题是leetcode中hard等级的，其实可以想到用两点法/滑动窗口法做，但具体操作并不容易想到（腾讯笔试遇到这个类似的题，gg），幸好leetcode上有大神已经帮我们整理好了子串搜索这一类问题的模板解：[Sliding Window algorithm template to solve all the Leetcode substring search problem][]

这里再结合代码解释一下这道题

class Solution(object):
        def minWindow(self, s, t):
            str_dict={
        }
            for i in t:		#建立目标子串的字符频数字典
                if i in str_dict:
                    str_dict[i]+=1
                else:
                    str_dict[i]=1
            left, cnt = 0, 0	# left为左指针，cnt为当前窗口中包含的目标子串的字符个数
            minlen = float('inf')
            res = ""
            for i in range(len(s)):		# 右指针
                if s[i] in str_dict:
                    str_dict[s[i]] -= 1
                    if str_dict[s[i]] >= 0:
                        cnt += 1
                # 上面部分是右指针一直在向右移动，直到窗口中包含了所有目标子串字符
                # 然后开始左指针向右移动，尝试减小窗口的大小
                while cnt==len(t):
                    if i-left+1<minlen:
                        minlen=i-left+1
                        res = s[left:left+minlen]
                    if s[left] in str_dict:
                        str_dict[s[left]]+=1
                        if str_dict[s[left]] > 0:
                            cnt -= 1
                    left+=1
            return res

举例. `S = "ABAACBAB" T = "ABC"`.

![76_Minimum_Window_Substring_2.png][]

找到一个解并记录下之后，会重复上面的步骤

![76_Minimum_Window_Substring_3.png][]  
图片参考：[https://leetcode.com/problems/minimum-window-substring/solution/][https_leetcode.com_problems_minimum-window-substring_solution]

最后附：

一个两点法的总结可以参见：[two pointer的运用][two pointer]

快慢指针参考：[链表环的入口结点][Link 1]

[Sliding Window algorithm template to solve all the Leetcode substring search problem]: https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.
[76_Minimum_Window_Substring_2.png]: https://leetcode.com/problems/minimum-window-substring/Figures/76/76_Minimum_Window_Substring_2.png
[76_Minimum_Window_Substring_3.png]: https://leetcode.com/problems/minimum-window-substring/Figures/76/76_Minimum_Window_Substring_3.png
[https_leetcode.com_problems_minimum-window-substring_solution]: https://leetcode.com/problems/minimum-window-substring/solution/
[two pointer]: http://chocoluffy.com/2016/12/04/%E6%B5%85%E6%9E%90%E7%BB%8F%E5%85%B8%E9%9D%A2%E8%AF%95%E7%AE%97%E6%B3%95%E9%A2%98-two-pointer%E7%9A%84%E8%BF%90%E7%94%A8/
[Link 1]: https://www.cnblogs.com/zhuzhenwei918/p/7491892.html