1.4 双序列双指针
约 1226 字大约 4 分钟
2024-11-22
1.4.1 双指针
class Solution: def getCommon(self, nums1: List[int], nums2: List[int]) -> int: p = q = 0 while p < len(nums1) and q < len(nums2): if nums1[p] == nums2[q]: return nums1[p] elif nums1[p] < nums2[q]: p += 1 else: q += 1 return -1时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。
空间复杂度：O(1)
如果我们从左往右按小的插入，会覆盖元素，因为空位在后面，因此，如果我们从右往左按大的插入，会更好操作一些
class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ i = m - 1 j = n - 1 k = m + n - 1 while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。
空间复杂度：O(1)
append：所见即所得，extend：迭代地添加
my_list = [1, 2, 3] my_list.append([5, 6]) # 输出: [1, 2, 3, 4, [5, 6]]my_list = [1, 2, 3] my_list.extend([5, 6]) # 输出: [1, 2, 3, 4, 5, 6]class Solution: def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]: res = [] p = q = 0 while 1: if q == len(nums2): res.extend(nums1[p:]) return res if p == len(nums1): res.extend(nums2[q:]) return res if nums1[p][0] == nums2[q][0]: res.append([nums1[p][0], nums1[p][1] + nums2[q][1]]) p += 1 q += 1 elif nums1[p][0] < nums2[q][0]: res.append(nums1[p]) p += 1 else: res.append(nums2[q]) q += 1时间复杂度：O(n + m)，其中 n 为 nums1 的长度，m 为 nums2 的长度。
空间复杂度：O(1)
一个指针从左往右遍历第一个数组，另一个指针从右往左遍历第二个数组
class Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: res = 0 staple.sort() drinks.sort() p = 0 q = len(drinks) - 1 while p < len(staple): if staple[p] + drinks[q] > x and q >= 0: q -= 1 else: res = res + q + 1 p += 1 return res % 1000000007时间复杂度：O(nlogn + mlogm + n + m) = O(nlogn + mlogm)，其中 n 为 staple 的长度，m 为 drinks 的长度。
空间复杂度：O(1)
枚举法
class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: res = 0 for i in range(len(arr1)): for j in range(len(arr2)): if abs(arr1[i] - arr2[j]) <= d: res -= 1 break res += 1 return res时间复杂度：O(n * m)
空间复杂度：O(1)
双指针法
class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: arr1.sort() arr2.sort() left ,right, res = 0, 0, 0 for num in arr1: while left < len(arr2) and arr2[left] + d < num: left += 1 while right < len(arr2) and arr2[right] - d <= num: right += 1 if left == right: res += 1 return res时间复杂度：O(nlogn)
空间复杂度：O(1)
class Solution: def maxDistance(self, nums1: List[int], nums2: List[int]) -> int: res = 0 j = 0 for i in range(len(nums1)): while j < len(nums2) and nums1[i] <= nums2[j]: j += 1 res = max(res, j - i - 1) return res时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def isLongPressedName(self, name: str, typed: str) -> bool: i = 0 j = 0 while j < len(typed): if i <len(name) and name[i] == typed[j]: i += 1 j += 1 elif j > 0 and name[i - 1] == typed[j]: j += 1 else: return False return i == len(name)时间复杂度：O(n)
空间复杂度：O(1)
1.4.2 判断子序列
提示
阿囧说：外层遍历长串，好的情况可以是没遍历完就找到了，最坏情况遍历完才知道不符合
class Solution: def isSubsequence(self, s: str, t: str) -> bool: if s == "": return True i = 0 for j in range(len(t)): if s[i] == t[j]: i += 1 if i == len(s): return True return False时间复杂度：O(m)，其中 m 是 t 的长度。代码只有一个循环，至多循环 O(m) 次。
空间复杂度：O(1)
class Solution: def findLongestWord(self, s: str, dictionary: List[str]) -> str: res = "" for dic in dictionary: dic_left = 0 for c in s: if c == dic[dic_left]: dic_left += 1 if dic_left == len(dic): if len(dic) > len(res) or (len(dic) == len(res) and dic < res): res = dic break return res时间复杂度：O(n * m)
空间复杂度：O(1)
class Solution: def appendCharacters(self, s: str, t: str) -> int: t_left = 0 for s_c in s: if s_c == t[t_left]: t_left += 1 if t_left == len(t): return 0 return len(t) - t_left时间复杂度：O(n)
空间复杂度：O(1)
class Solution: def canMakeSubsequence(self, str1: str, str2: str) -> bool: str2_left = 0 for c in str1: if c == str2[str2_left] or (ord(str2[str2_left]) - ord(c) + 26) % 26 == 1: str2_left += 1 if str2_left == len(str2): return True return False时间复杂度：O(n)
空间复杂度：O(1)