双指针&滑动窗口

preface:

双指针：
通常一个 left 指针，一个 right 指针，指针同向移动或异向移动。这类问题通常都是基于暴力解法的优化。

滑动窗口:
通常是一类双指针同向移动的问题。

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        lookup = set()
        l = 0
        ans = 0

        for r in range(len(s)):
            while s[r] in lookup:
                lookup.remove(s[l])
                l += 1
            ans = max(ans, r-l+1)
            lookup.add(s[r])

        return ans

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0。请你找出所有和为 0 且不重复的三元组。

先固定住a， 再使用双指针

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = [] 

        for a in range(n):
            if a>0 and nums[a] == nums[a-1]:
                continue
            c = n-1
            target = -nums[a]

            for b in range(a+1, n):
                if b>a+1 and nums[b] == nums[b-1]:
                    continue
                while b < c and nums[b]+nums[c] > target:
                    c -= 1
                if b == c:
                    break
                if nums[b] + nums[c] == target:
                    ans.append([nums[a], nums[b], nums[c]])

        return ans

18. 四数之和

与三数之和类似，排序 + 双指针，麻了。。。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n < 4: return [] 
        nums.sort()
        res = []

        for a in range(n):
            if a>0 and nums[a] == nums[a-1]:          #固定住a
                continue
            for b in range(a+1, n):
                if b>a+1 and nums[b] == nums[b-1]:    #固定住b
                    continue
                k = target - nums[a] - nums[b]
                d = n-1                               # 双指针右边
                for c in range(b+1, n):               # 双指针左边
                    if c>b+1 and nums[c] == nums[c-1]:
                        continue
                    while c < d and nums[c]+nums[d]>k:
                        d -= 1
                    if d == c:
                        break
                    if nums[c] + nums[d] == k:
                        res.append([nums[a], nums[b], nums[c], nums[d]])
        
        return res

26. 删除有序数组中的重复项

left 指针存放当前的空位

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 0
        for i,num in enumerate(nums):
            if l==0 or num != nums[i-1]:  # i 换成 l 也行
                nums[l] = num
                l += 1
        return l

80. 删除有序数组中的重复项 II

slow 指针存放当前的空位

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = 2
        for fast in range(2, len(nums)):
            if nums[fast] != nums[slow-2]:
                nums[slow] = nums[fast]
                slow += 1
        return slow

42. 接雨水

该题还有多种做法：动态规划，单调栈

class Solution:
    def trap(self, height: List[int]) -> int:
        # 边界条件
        if not height: return 0
        n = len(height)

        left, right = 0, n - 1  
        maxleft,maxright = height[0],height[n - 1]
        ans = 0

        while left <= right:
            maxleft = max(height[left],maxleft)
            maxright = max(height[right],maxright)
            if maxleft < maxright:
                ans += maxleft - height[left]
                left += 1
            else:
                ans += maxright - height[right]
                right -= 1

        return ans

407. 接雨水 II

Dijkstra + 优先队列

567. 字符串的排列

判断 s1 的排列之一是 s2 的子串。

class Solution(object):
    def checkInclusion(self, s1, s2):
        l, r = 0, len(s1)-1
        c1 = Counter(s1)
        c2 = Counter(s2[0:r])

        while r < len(s2):
            c2[s2[r]] += 1
            if c1 == c2:
                return True
            c2[s2[l]] -= 1
            if c2[s2[l]] == 0:
                del c2[s2[l]]
            l += 1
            r += 1

        return False

# 暴力解法的优化

159. 至多包含两个不同字符的最长子串⭐

给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t ，并返回该子串的长度。

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        n = len(s)
        if n < 3: return n

        h = {}             #记录字母最后出现的位置
        l, r = 0, 0        #滑动窗口指针
        res = 2
        for r in range(n):
            h[s[r]] = r
            if len(h) == 3:  # r刚走出滑动窗口
                idx = min(h.values())
                del h[s[idx]]
                l = idx + 1
            res = max(res, r - l + 1)
        return res

经典滑动窗口

340. 至多包含 K 个不同字符的最长子串

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if n < k: return n

        h = {}             #记录字母最后出现的位置
        l, r = 0, 0        #滑动窗口指针
        res = 0
        for r in range(n):
            h[s[r]] = r
            if len(h) == k+1:  # r刚走出滑动窗口
                idx = min(h.values())
                del h[s[idx]]
                l = idx + 1
            res = max(res, r - l + 1)
        return res

与上一道题相同