6. Two Pointers - swchen1234/Algorithm GitHub Wiki

理论

题型分类

1.前向型指针
- 1.1 窗口型 Sliding Window
- 1.2 快慢型 * 1.2.1 读写指针 * 1.2.2 龟兔赛跑 * 1.2.3 Linked List
- 1.3 Iterator
2.相向型只要数组有序，就应该想到双指针技巧
- 2.1 Two Sums
- 2.2 其它
- 2.3 分成三个部分 - Dutch National Flag Problem
- 2.4 二分查找
3.背向型
4.两个数组

题目

1.前向型指针

1.1 窗口型 Sliding Window

j = 0
for i = 0 ... n:
    while j < n and 满足条件:
           更新答案；
           j++
     更新状态

j = 0
for i = 0 ... n:
    while j < n and 不满足条件:
           更新状态           
           j++
     更新答案

1.1.1 求max/longest

=> while(不满足条件):{不断更新i}, 更新答案

3. Longest Substring Without Repeating Characters 用set来存放窗口中的字母 =>用mp[c]存放字母最近一次出现位置，则更新是i = max(i, mp[c])
159. Longest Substring with At Most Two Distinct Characters
340. Longest Substring with At Most K Distinct Characters完全同159
424. Longest Repeating Character Replacement 用defaultdict存窗口中字母出现次数.类似于3.
2781. Length of the Longest Valid Substring 遍历word[j-k:j], k=1...10, 若属于forbidden, 更新i
904. Fruit Into Baskets
567. Permutation in String 用一个unmatchedCount优化做sliding window
424. Longest Repeating Character Replacement用cnt[26]记录每个字母出现次数， max(cnt)得不需替代的词 1004. Max Consecutive Ones III 1493. Longest Subarray of 1's After Deleting One Element 几乎同1004
1679. Max Number of K-Sum Pairs
1838. Frequency of the Most Frequent Element窗口中要增加的总和为nums[j]*(j-i+1) - sum(nums[i...j]), 不断右移i，直至符合条件。O(nlgn)\

1.1.2 求min/shortest

=> while(满足条件):{更新答案，不断更新i}

30. Substring with Concatenation of All Words 因为单词长度相同，遍历右指针起始位置[n, 2n), 每次移动wordLen格，更新wordDict, while wordDict[w] > wordCnt[w], 更新左指针。
209. Minimum Size Subarray Sum
2009. Minimum Number of Operations to Make Array Continuous对unique value排序，以每个value（左指针）为最小值，移动右指针直至超过value + n，则左右指针之内的元素不用改变，其它元素要改变，n - (j - i).
1658. Minimum Operations to Reduce X to Zero化为求最大子窗口，使得其和== total - x\

几乎用一样的方法： 76. Minimum Window Substring 移动右指针，while 满足条件，更新答案，直至不满足。满足条件用match个数来判断。
567. Permutation in String 438. Find All Anagrams in a String

1.1.3 Count

=> 上述两者皆有，res+= ...

713. Subarray Product Less Than K
2302. Count Subarrays With Score Less Than K
2962. Count Subarrays Where Max Element Appears at Least K Times每次固定右端点后，移动左端点，直至不满足条件，res += left
2444. Count Subarrays With Fixed Bounds 同2962，记录最近越界指数，minK指数，maxK指数，越界指数到min(maxPosition,minPosition)之间的距离。
532. K-diff Pairs in an Array因为只需unique,故发现match后左指针要跳过所有相同元素.
611. Valid Triangle Number固定一端i（从左-》右，或从右-〉左均可),另遍历j(from j=i+1)，k=i+2，移动k直到符合条件\

2762. Continuous Subarrays维持窗口的最大最小值。法一：用maxheap, minheap存（val, idx), O(nlgn)。法二：用两个单调deque,存min, max，O(n)；右指针移动是不断缩小有效范围，若超出范围，设左指针=右指针-1，向左移动，直到超出范围。O(n).
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit完全同2762
992. Subarrays with K Different Integers

法一：化为atmost(k) - atmost(k-1) 法一：one pass. 每移动一步r，while distinct>k{移动l}；若distinct==k, 若cache[l]>1, 说明还能移动l, dup+=1, 代表除了最小窗口加上l也能成立，直至l不能移动；res+=dup+1

930. Binary Subarrays With Sumprefix sum最容易；另外可以用992的两种方法\

1.1.4 Robin Karp

28. Find the Index of the First Occurrence in a String 187. Repeated DNA Sequences Robin Karp来hash过去见过的长度为10的子串，base=base*4 + mp[s[i]] - mp[s[i-10]]*(4**10)

1.1.5 Others

220. Contains Duplicate III将窗口中元素放在bucket中，每个bucket中之多只能存一个元素，因为一旦两个元素位于同一bucket,返回true；每次检查当前bucket,以及左右bucket是否和当前数之差小于diff\ #bucket_sort 39. Sliding Window Maximum 单调减deque，左边pop出左指针，右边pop出比右指针小的元素 #monotonic_deque
995. Minimum Number of K Consecutive Bit Flips 用flipped = []来表示nums[i]是否flip过(目的是移动左端点时，判断flipCnt是否需要减一），同时flipCnt表示当前窗口flip的次数,若flipCnt%2==nums[i],则需要flip。
161. One Edit Distance当s[i]!= t[j]时，若len(s)较长，判断s[i+1:]==t[j:];否则，判断s[i+1:]==t[j+1:]
560. Subarray Sum Equals K Note that since elements can be negative, two pointers does not work here.
845. Longest Mountain in Array设左右指针，while循环内，1)移动左指针到不再>=，更新左指针，令右=左 2)移动右指针到不再上坡 3)移动右指针到不再下坡，更新答案 26. Remove Duplicates from Sorted Array 2524. Maximum Frequency Score of a Subarray固定窗口size, 计算power时，使用pow(val, k, MOD)可以对power结果取模
2134. Minimum Swaps to Group All 1's Together II固定窗口长度为array中所有1的个数，这样只需判断subarray中0的个数，即为需要swap的个数；用双指针遍历所有subarray，找到最小0的个数\

1.2 快慢型

1.2.1 读写指针（原地修改）

以下几道题用的方法一样： 27. Remove Element 26. Remove Duplicates from Sorted Array 83. Remove Duplicates from Sorted List 283. Move Zeroes当有很多零，最快的方法是，用一个firstZero指针, 当curr指向非零时，交换两者，是的firstZero指针向右移一位。

1.2.2 龟兔赛跑

287. Find the Duplicate Number设快慢指针找循环入口

1.2.3 Linked List

e.g. 应用： 1、合并两个有序链表 2、链表的分解 3、合并 k 个有序链表 4、寻找单链表的倒数第 k 个节点 5、寻找单链表的中点 6、判断单链表是否包含环并找出环起点 7、判断两个单链表是否相交并找出交点

457. Circular Array Loop 19. Remove Nth Node From End of List

1.3 Iterator

251. Flatten 2D VectoradvanceToNext() helper method that checks if the current inner and outer values point to an integer; hasNext()和next()都调用次函数，用res占存结果，然后j += 1, 返回res.

2. 相向型

2.1 Two Sums

法一: Two pointer, 先排序，左右各一指针 (必须所有元素为正）

for i = 0 ... n:
    while j > i and 满足条件:
           更新答案；
           j--
     更新状态

法二: Hash.

15. 3Sum'双指针和hash的时间复杂度均为O(n^2)\ [18. 4Sum](https://leetcode.com/problems/4sum/)recursion 直至2sum, 用hash或2pointer解。O(n^(k-1))for k-sum\ [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/)只能用2pointer解\ [259. 3Sum Smaller](https://leetcode.com/problems/3sum-smaller/)遍历i, 设置j, k向当中移，若符合条件,res += k - j\ [2964. Number of Divisible Triplet Sums](https://leetcode.com/problems/number-of-divisible-triplet-sums/)尽管类似15，但只能用hash\ [1099. Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)\ [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)当k sum时，则用backtracking解.`\

1679. Max Number of K-Sum Pairs同2sum, 1)相像双指针 2）hash
two-sum-less-than-or-equal-to-target 以left 为anchor point, move right from the right end until 'left + right < target', 满足的个数为 right - left.\

2.2 其它

11. Container With Most Water
42. Trapping Rain Water记录leftPtr 和 rightPtr, currHeight
680. Valid Palindrome II出现不match后，return f(i+1, j) or f(i, j-1)
948. Bag of Tokens贪心算法
881. Boats to Save People左右指针, 移动右指针，若p[i]+p[j]<=limit, 则左右两个指针都移动，否则只移动右指针
786. K-th Smallest Prime Fraction左右指针+heap

2.3 分成三个部分 - Dutch National Flag Problem

设立读写r, 左右0， 2边界（两指针都指在1的范围内）指针i, j。从左到右遍历r，如下交换。

r, i, j = 0, 0, len(nums) - 1
while r <= j:
if nums[r] == 0:
    nums[r], nums[i] = nums[i], nums[r]
    i += 1  // 因为j位于r的右边，j所指的数还未处理，所以j所指的数可能为0， 交换后仍需处理；
    r += 1
elif nums[r] == 2:
    nums[r], nums[j] = nums[j], nums[r]               
    j -= 1  // i处于r左边，已经处理，i所指的数为1，故交换后无需再处理，故r += 1;
else:
    r += 1  // 对于r指在1上，无需交换，同样也要r += 1.

75. Sort Colors

3 背向型

5. Longest Palindromic Substring 遍历每个字母，以其为1）中心靠左 2）中心展开

4 两个数组

两个同向指针分别指向两个数组

4.1 找到最小距离

244. Shortest Word Distance IImp[word]=[index list]，两个指针分别指向mp[word1]和mp[word2]，依<>移动 475. Heaters等价于找到每个点到另一个数组的最短距离，在heater数组左右两端加上inf, -inf，更易操作

4.2 合并

321. Create Maximum Number分为(1)对于每个i, 找到num1, num2中的single array max(单调栈实现), 大小分别为i, k-i (2)合并，这里不能单纯用sorted array的合并方法，而是应该每添加一个，比较nums1[i:], nums2[j:]. （3），找到这么多（1）+（2）组合中最大数组。

4.3 match

408. Valid Word Abbreviation 1868. Product of Two Run-Length Encoded Arrays设cumRemain, 当其=0时，i+1或者j+1\

826. Most Profit Assigning Work扫描线+双指针
2337. Move Pieces to Obtain a String两个指针都从最左开始，分别找到下一个不是'_'的字符，比较是否相同以及指数大小
777. Swap Adjacent in LR String完全同2337\