一、基础算法精讲：双指针

1、相向双指针 1

1.1 两数之和 II - 输入有序数组

Leetcode 167

注意，这里可以使用相向双指针的原因是因为这里的数组是非递减的。

class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:l = 0r = len(numbers) - 1while True:s = numbers[l] + numbers[r]if s == target:return [l + 1, r + 1]if s > target:r -= 1else:l += 1

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size() - 1;while (true) {int s = numbers[l] + numbers[r];if (s == target) return {l + 1, r + 1};s > target ? r -- : l ++ ;}}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

1.2 三数之和

Leetcode 15

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()ans = []n = len(nums)for i in range(n - 2):x = nums[i]if i > 0 and x == nums[i - 1]:  # 跳过重复数字continueif x + nums[i + 1] + nums[i + 2] > 0:  # 优化一breakif x + nums[-2] + nums[-1] < 0:  # 优化二continuej = i + 1k = n - 1while j < k:s = x + nums[j] + nums[k]if s > 0:k -= 1elif s < 0:j += 1else:ans.append([x, nums[j], nums[k]])j += 1while j < k and nums[j] == nums[j - 1]:  # 跳过重复数字j += 1k -= 1while k > j and nums[k] == nums[k + 1]:  # 跳过重复数字k -= 1return ans

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> ans;int n = nums.size();for (int i = 0; i < n - 2; i ++ ) {int x = nums[i];if (i && x == nums[i - 1]) continue;  // 跳过重复数字if (x + nums[i + 1] + nums[i + 2] > 0) break;  // 优化一if (x + nums[n - 1] + nums[n - 2] < 0) continue;  // 优化二int j = i + 1, k = n - 1;while (j < k) {int s = x + nums[j] + nums[k];if (s > 0) k -- ;else if (s < 0) j ++ ;else {ans.push_back({x, nums[j], nums[k]});for ( ++ j; j < k && nums[j] == nums[j - 1]; j ++ );  // 跳过重复元素for ( -- k; k > j && nums[k] == nums[k + 1]; k -- );  // 跳过重复元素}}}return ans;}
}; 

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

1.3 最接近的三数之和

Leetcode 16

注意这里的三个优化：

class Solution:def threeSumClosest(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)minDiff = infans = 0for i in range(n - 2):x = nums[i]# 优化三if i and x == nums[i - 1]: continue# 优化一s = x + nums[i + 1] + nums[i + 2]if s > target:if s - target < minDiff:minDiff = s - targetans = sbreak# 优化二s = x + nums[-1] + nums[-2]if s < target:if target - s < minDiff:minDiff = target - sans = scontinuej, k = i + 1, n - 1while j < k:s = x + nums[j] + nums[k]if s == target:return sif s > target:      if s - target < minDiff:minDiff = s - targetans = s      k -= 1 else:if target - s < minDiff:minDiff = target - sans = sj += 1return ans

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {int res;int min_diff = 1e9;int n = nums.size();sort(nums.begin(), nums.end());for (int i = 0; i < n - 2; i ++ ) {int x = nums[i];// 优化一if (i && x == nums[i - 1]) continue;// 优化二int s = x + nums[i + 1] + nums[i + 2];if (s > target) {if (s - target < min_diff) min_diff = s - target, res = s;break;}// 优化三s = x + nums[n - 2] + nums[n - 1];if (s < target) {if (target - s < min_diff)min_diff = target - s, res = s;continue;}int j = i + 1, k = n - 1;while (j < k) {s = x + nums[j] + nums[k];if (s == target) return s;if (s > target) {if (s - target < min_diff)min_diff = s - target, res = s;k -- ;} else {if (target - s < min_diff)min_diff = target - s, res = s;j ++ ;}}}return res;}
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

1.4 四数之和

Leetcode 18

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()n = len(nums)ans = []for a in range(n - 3):x = nums[a]if a and x == nums[a - 1]: continueif x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target: breakif x + nums[-1] + nums[-2] + nums[-3] < target: continue;for b in range(a + 1, n - 2):y = nums[b]if b > a + 1 and y == nums[b - 1]: continueif x + y + nums[b + 1] + nums[b + 2] > target: breakif x + y + nums[-1] + nums[-2] < target: continuec, d = b + 1, n - 1while c < d:s = x + y + nums[c] + nums[d]if s > target: d -= 1elif s < target: c += 1else: ans.append([x, y, nums[c], nums[d]])c += 1while c < d and nums[c] == nums[c - 1]: c += 1d -= 1while c < d and nums[d] == nums[d + 1]: d -= 1return ans

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;int n = nums.size();sort(nums.begin(), nums.end());for (int a = 0; a < n - 3; a ++ ) {long long x = nums[a];if (a && x == nums[a - 1]) continue;if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;if (x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;for (int b = a + 1; b < n - 2; b ++ ) {long long y = nums[b];if (b > a + 1 && y == nums[b - 1]) continue;if (x + y + nums[b + 1] + nums[b + 2] > target) break;if (x + y + nums[n - 1] + nums[n - 2] < target) continue;int c = b + 1, d = n - 1;while (c < d) {long long s = x + y + nums[c] + nums[d];if (s < target) c += 1;else if (s > target) d -= 1;else {ans.push_back({(int)x, (int)y, nums[c], nums[d]});for (c ++ ; c < d && nums[c] == nums[c - 1]; c ++ );for (d -- ; c < d && nums[d] == nums[d + 1]; d -- );}}  }}return ans;}
};

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(1)$

1.5 统计和小于目标的下标对数目

Leetcode 2824

class Solution:def countPairs(self, nums: List[int], target: int) -> int:nums.sort()n = len(nums)l, r = 0, n - 1ans = 0while l < r:if nums[l] + nums[r] < target:ans += r - ll += 1else:r -= 1return ans

class Solution {
public:int countPairs(vector<int>& nums, int target) {int n = nums.size();sort(nums.begin(), nums.end());int l = 0, r = n - 1, ans = 0;while (l < r) if (nums[l] + nums[r] < target)ans += r - l, l += 1;else r -= 1;return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

1.6 有效三角形的个数

Leetcode 611

class Solution:def triangleNumber(self, nums: List[int]) -> int:nums.sort()n = len(nums)ans = 0for k in range(2, n):c = nums[k]l, r = 0, k - 1while l < r:if nums[l] + nums[r] > c:ans += r - lr -= 1else:l += 1return ans

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size();int ans = 0;for (int k = 2; k < n; k ++ ) {int c = nums[k];int l = 0, r = k - 1;while (l < r) if (nums[l] + nums[r] > c)ans += r - l, r -= 1;else l += 1;}return ans;}
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

2、相向双指针 2

2.1 盛最多水的容器

Leetcode 11

class Solution:def maxArea(self, height: List[int]) -> int:ans = l = 0r = len(height) - 1while l < r:area = (r - l) * min(height[l], height[r])ans = max(ans, area)if height[l] < height[r]:l += 1else:r -= 1return ans

class Solution {
public:int maxArea(vector<int>& height) {int ans = 0, l = 0, r = height.size() - 1;while (l < r) {int area = (r - l) * min(height[l], height[r]);ans = max(area, ans);if (height[l] < height[r]) l += 1;else r -= 1;}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

2.2 接雨水

Leetcode 42

解法一：前后缀分解

class Solution:def trap(self, height: List[int]) -> int:n = len(height)pre_max = [0] * npre_max[0] = height[0]for i in range(1, n):pre_max[i] = max(height[i], pre_max[i - 1])suf_max = [0] * nsuf_max[-1] = height[-1]for i in range(n - 2, -1, -1):suf_max[i] = max(height[i], suf_max[i + 1])ans = 0for h, pre, suf in zip(height, pre_max, suf_max):ans += min(pre, suf) - hreturn ans

class Solution {
public:int trap(vector<int>& height) {int n = height.size();vector<int> pre_max(n);pre_max[0] = height[0];for (int i = 1; i < n; i ++ )pre_max[i] = max(height[i], pre_max[i - 1]);vector<int> suf_max(n);suf_max[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i -- )suf_max[i] = max(height[i], suf_max[i + 1]);int ans = 0;for (int i = 0; i < n; i ++ ) ans += min(pre_max[i], suf_max[i]) - height[i];return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

解法二：双指针

class Solution:def trap(self, height: List[int]) -> int:ans = l = pre_max = suf_max = 0r = len(height) - 1while l < r:pre_max = max(pre_max, height[l])suf_max = max(suf_max, height[r])if pre_max < suf_max:ans += pre_max - height[l]l += 1else:ans += suf_max - height[r]r -= 1return ans

class Solution {
public:int trap(vector<int>& height) {int l = 0, ans = 0, pre_max = 0, suf_max = 0, r = height.size() - 1;while (l < r) {pre_max = max(pre_max, height[l]);suf_max = max(suf_max, height[r]);if (pre_max < suf_max)ans += pre_max - height[l], l += 1;else ans += suf_max - height[r], r -= 1;}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

解法三：单调栈

注意：一个凹槽由三个位置决定【最左边（$height[left]$），中间（$botto{m}_h$），最右边（$h$）】

class Solution:def trap(self, height: List[int]) -> int:ans = 0st = []for i, h in enumerate(height):while st and h >= height[st[-1]]:  # 表示可以形成一个凹槽bottom_h = height[st.pop()]    # 弹出栈顶元素并赋值给bottom_hif not st:                     # 没有左边界breakleft = st[-1]dh = min(height[left], h) - bottom_h  # 高度差ans += dh * (i - left - 1)st.append(i)return ans

class Solution {
public:int trap(vector<int>& height) {int ans = 0;stack<int> st;for (int i = 0; i < height.size(); i ++ ) {while (!st.empty() && height[i] >= height[st.top()]) {int bottom_h = height[st.top()];st.pop();if (st.empty()) break;int left = st.top();int dh = min(height[left], height[i]) - bottom_h;ans += dh * (i - left - 1);}st.push(i);}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(min(U,n))$，其中 $U=max(height)-min(height)+1$

3、同向双指针：滑动窗口（区间大小可变）

3.1 长度最小的子数组

Leetcode 209

这里能够使用双指针是因为 $while$ 条件中是满足单调性的

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)ans = infs = left = 0for right, x in enumerate(nums):s += xwhile s >= target:ans = min(ans, right - left + 1)s -= nums[left]left += 1return ans if ans <= n else 0

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), ans = n + 1, s = 0, left = 0;for (int right = 0; right < n; right ++ ) {s += nums[right];while (s >= target) {ans = min(ans, right - left + 1);s -= nums[left ++ ];}}return ans <= n ? ans : 0;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

3.2 乘积小于 K 的子数组

Leetocde 713

class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:if k <= 1: return 0ans = l = 0prod = 1for r, x in enumerate(nums):prod *= xwhile prod >= k:prod /= nums[l]l += 1ans += r - l + 1return ans

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if (k <= 1) return 0;int n = nums.size(), ans = 0, prod = 1, left = 0;for (int right = 0; right < n; right ++ ) {prod *= nums[right];while (prod >= k) prod /= nums[left ++ ];ans += right - left + 1;}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

3.3 无重复字符的最长字串

Leetcode 3

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:ans = l = 0w = set()for r, c in enumerate(s):while c in w:w.remove(s[l])l += 1w.add(c)ans = max(ans, r - l + 1)return ans

python 另一个版本，效率比上面一个略微差一点：

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:ans = 0cnt = Counter()left = 0for right, c in enumerate(s):cnt[c] += 1while cnt[c] > 1:cnt[s[left]] -= 1left += 1ans = max(ans, right - left + 1)return ans

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size(), ans = 0, l = 0;unordered_set<char> w;for (int r = 0; r < n; r ++ ) {char c = s[r];while (w.count(c)) w.erase(s[l ++ ]);w.insert(c);ans = max(ans, r - l + 1);}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(128)\approx O(1)$

3.4 最大连续1的个数 III

Leetcode 1004

class Solution:def longestOnes(self, nums: List[int], k: int) -> int:ans = left = cnt0 = 0  # cnt0 用于统计窗口内部0的个数for right, x in enumerate(nums):cnt0 += 1 - xwhile cnt0 > k:cnt0 -= 1 - nums[left]left += 1ans = max(ans, right - left + 1)return ans

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size(), l = 0, ans = 0, cnt0 = 0;for (int r = 0; r < n; r ++ ) {cnt0 += 1 - nums[r];while (cnt0 > k) cnt0 -= 1 - nums[l ++ ];ans = max(ans, r - l + 1);}return ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

3.5 替换子串得到平衡字符串

Leetcode 1234

如果在 待替换子串（即滑动窗口） 之外的任意字符的出现次数超过 $m=\frac{n}{4}$，那么无论怎么替换，都无法使这个字符的出现次数等于 $m$。

反过来说，如果在待替换子串之外的任意字符的出现次数都不超过 $m$，那么可以通过替换，使 $s$ 为平衡字符串，即每个字符的出现次数均为 $m$。

class Solution:def balancedString(self, s: str) -> int:cnt, m = Counter(s), len(s) // 4# 用于判断可迭代对象中的所有元素是否都为真if all(cnt[x] == m for x in "QWER"): return 0ans, left = inf, 0for right, c in enumerate(s):cnt[c] -= 1while all(cnt[x] <= m for x in "QWER"):ans = min(ans, right - left + 1)cnt[s[left]] += 1left += 1return ans

class Solution {
public:int balancedString(string s) {int n = s.length(), m = n / 4, cnt['X']{};for (char c: s) cnt[c] ++ ;if (cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m)return 0;int ans = n, l = 0;for (int r = 0; r < n; r ++ ) {cnt[s[r]] -- ;while (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {ans = min(ans, r - l + 1);cnt[s[l ++ ]] ++ ;}}return ans;}
};

• 时间复杂度：$O(CN)$，其中 $C=4$，$N$ 为字符串 $s$ 的长度
• 空间复杂度：$O(C)$

3.6 将 x 减到 0 的最小操作数

Leetcode 1658

逆向思维

将原问题转换为求解数组中最长的子数组，使得子数组的元素和为 $s-x$，其中 $s$ 表示整个数组的和。

class Solution:def minOperations(self, nums: List[int], x: int) -> int:target = sum(nums) - xif target < 0: return -1ans = -1  # 存储长度left = s = 0  # s 存储窗口内的和for right, x in enumerate(nums):s += xwhile s > target:s -= nums[left]left += 1if s == target:ans = max(ans, right - left + 1)return -1 if ans < 0 else len(nums) - ans

class Solution {
public:int minOperations(vector<int>& nums, int x) {int target = accumulate(nums.begin(), nums.end(), 0) - x;if (target < 0) return -1;int ans = -1, l = 0, sum = 0, n = nums.size();for (int r = 0; r < n; r ++ ) {sum += nums[r];while (sum > target) sum -= nums[l ++ ];if (sum == target) ans = max(ans, r - l + 1);}        return ans < 0 ? -1 : n - ans;}
};

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$