2025-2-10-4.4 双指针（基础题1）

4.4 双指针（基础题）

作者：灵茶山艾府

链接：https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/

跟滑动窗口有点像，不过，别具特色，while 循环用得比较频繁，难得地方是循环中的 条件判断，if语句后面的内容不是特别好想。

344. 反转字符串

题目：344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

举例：

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示:

• 1 <= s.length <= 10^5
• s[i] 都是 ASCII 码表中的可打印字符

代码：

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""'''时间复杂度：O(n)，n为s的长度空间复杂度：O(1)'''l,h = 0,len(s)-1# 这个 while 循环很有趣哦。while l < h:s[l],s[h] = s[h],s[l]l += 1h -= 1

125. 验证回文串

题目：125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

举例：

示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。示例 2：
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

提示:

• 1 <= s.length <= 2 * 10^5
• s 仅由可打印的 ASCII 字符组成

代码：

class Solution:def isPalindrome(self, s: str) -> bool:'''大写 upper()小写 lower()是字母 isalpha()是数字 isnumeric()时间复杂度：O(n)，n是s的长度空间复杂度：O(1)'''w = ""for c in s:if c.isalpha() | c.isnumeric():w += c.lower()print(w)l,h = 0,len(w)-1while l < h:if w[l] != w[h]:return Falsel += 1h -= 1return True         

1750. 删除字符串两端相同字符后的最短长度

题目：1750. 删除字符串两端相同字符后的最短长度

给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：

1. 选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
2. 选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
3. 前缀和后缀在字符串中任意位置都不能有交集。
4. 前缀和后缀包含的所有字符都要相同。
5. 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

举例：

示例 1：
输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。示例 2：
输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。示例 3：
输入：s = "aabccabba"
输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，得到 s = "cca" 。

提示:

• 1 <= s.length <= 10^5
• s 只包含字符 'a'，'b' 和 'c' 。

代码：

class Solution:def minimumLength(self, s: str) -> int:'''时间复杂度：O(n)，n为s的长度空间复杂度：O(1)'''i, j = 0, len(s)-1# 条件3，4，5while i < j and s[i] == s[j]:# 条件1while i + 1 < j and s[i] == s[i+1]:i += 1# 条件2while i < j - 1 and s[j-1] == s[j]:j -= 1i,j = i + 1, j - 1return max(0,j - i + 1) 

167.两数之和 II - 输入有序数组

题目：167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

举例：

示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

代码：

class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:'''时间复杂度：O(n)，n为numbers的长度空间复杂度：O(1)'''n = len(numbers)l , h = 0,n-1while l < h:if numbers[l] + numbers[h] < target:l += 1elif numbers[l] + numbers[h] > target:h -= 1else:# 记着跳出循环！breakreturn [l+1,h+1]

2105. 给植物浇水 II

题目：2105. 给植物浇水 II

Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。

每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：

• Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
• 无论需要多少水，为每株植物浇水所需的时间都是相同的。
• 如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
• 如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。

举例：

示例 1：
输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
输出：1
解释：
- 最初，Alice 和 Bob 的水罐中各有 5 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
- Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。示例 2：
输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4
输出：2
解释：
- 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。
- Alice 给植物 0 浇水，Bob 给植物 3 浇水。
- Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。
- 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。示例 3：
输入：plants = [5], capacityA = 10, capacityB = 8
输出：0
解释：
- 只有一株植物
- Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。

提示:

• n == plants.length
• 1 <= n <= 10^5
• 1 <= plants[i] <= 10^6
• max(plants[i]) <= capacityA, capacityB <= 10^9

代码：

class Solution:def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:'''时间复杂度：O(n)，n为plants的长度空间复杂度：O(1)'''ans = 0a, b = capacityA, capacityBi, j = 0, len(plants)-1while i < j:# Alice watered plant Aif a < plants[i]:ans += 1a = capacityAa -= plants[i]i += 1# Bob watered plant Bif b < plants[j]:ans += 1b = capacityBb -= plants[j]j -= 1# if Alice meets Bobif i == j and max(a,b) < plants[i]:ans += 1return ans

977. 有序数组的平方

题目：977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

举例：

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按 非递减顺序 排序

代码：

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:'''时间复杂度：O(n)，n为nums的长度空间复杂度：O(1)'''n = len(nums)ans = [0]*nl, h = 0, n-1for i in range(n-1,-1,-1):x = nums[l] * nums[l]y = nums[h] * nums[h]if x > y:ans[i] = xl += 1else:ans[i] = yh -= 1return ans

658. 找到K个最接近的元素

题目：658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

• |a - x| < |b - x| 或者
• |a - x| == |b - x| 且 a < b

举例：

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]示例 2：
输入：arr = [1,1,2,3,4,5], k = 4, x = -1
输出：[1,1,2,3]

提示:

• 1 <= k <= arr.length
• 1 <= arr.length <= 10^4
• arr 按 升序 排列
• -10^4 <= arr[i], x <= 10^4

代码：

class Solution:def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:'''时间复杂度：O(n)，n为数组arr的长度空间复杂度：O(1)'''# 双指针l, h = 0, len(arr)-1while l < h:l_t, h_t = abs(arr[l]-x), abs(arr[h]-x)# The threshold condition 1 —— number kif h - l + 1 > k:# Whoever is father away should move.if h_t >= l_t:h -= 1else:l += 1else:breakreturn arr[l:h+1]

1471. 数组中的k个最强值（与658异曲同工之妙）

题目：1471. 数组中的 k 个最强值

给你一个整数数组 arr 和一个整数 k 。

设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：

• |arr[i] - m| > |arr[j] - m|
• |arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]

请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。

中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2) 的元素。

• 例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
• 例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。

举例：

示例 1：
输入：arr = [1,2,3,4,5], k = 2
输出：[5,1]
解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。
注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。示例 2：
输入：arr = [1,1,3,5,5], k = 2
输出：[5,5]
解释：中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。示例 3：
输入：arr = [6,7,11,7,6,8], k = 5
输出：[11,8,6,6,7]
解释：中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。
[11,8,6,6,7] 的任何排列都是正确答案。示例 4：
输入：arr = [6,-3,7,2,11], k = 3
输出：[-3,11,2]示例 5：
输入：arr = [-7,22,17,3], k = 2
输出：[22,17]

提示:

• 1 <= arr.length <= 10^5
• -10^5 <= arr[i] <= 10^5
• 1 <= k <= arr.length

代码：

class Solution:def getStrongest(self, arr: List[int], k: int) -> List[int]:'''时间复杂度：O(n)， n为arr的长度空间复杂度：O(1)'''n = len(arr)arr.sort()ans = []x = arr[(n-1)//2]l, h = 0, n-1while h - l + 1 > n - k:if arr[h] - x >= x - arr[l]:ans.append(arr[h])h -= 1else:ans.append(arr[l])l += 1return ans

633. 平方数之和（isqrt()函数）

题目：633. 平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

举例：

示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5示例 2：
输入：c = 3
输出：false

提示:

• 0 <= c <= 2^31 - 1

代码：

class Solution:def judgeSquareSum(self, c: int) -> bool:'''时间复杂度：O(isqrt(c))空间复杂度：O(1)'''a, b = 0 , isqrt(c)while a < b:s = a * a + b * bif s < c:a += 1elif s > c:b -= 1else:return Truereturn False

2824. 统计和小于目标的下标对数目

题目：2824. 统计和小于目标的下标对数目

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。

举例：

示例 1：
输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。示例 2：
输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个下标对满足题目描述：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示:

• 1 <= nums.length == n <= 50
• -50 <= nums[i], target <= 50

代码：

class Solution:def countPairs(self, nums: List[int], target: int) -> int:'''时间复杂度：O(nlogn)，其中 n 为 nums 的长度。瓶颈在排序上。空间复杂度：O(1)。不计入排序的栈开销，仅用到若干额外变量。'''nums.sort()ans = 0n = len(nums)l, h = 0, n-1while l < h:s = nums[l] + nums[h]if s >= target:h -= 1else:ans += h -ll += 1return ans