第11-12天打卡，附上學習鏈接
1 學習內(nèi)容
1.1 雙指針（Two Pointers）
雙指針指的是在遍歷元素的過程中，使用兩個指針，方向相反稱之為對撞指針，方向相同則稱之快慢指針，如果屬于不同的數(shù)組/鏈表，則稱之為分離雙指針。在數(shù)組的區(qū)間問題上，雙指針可以將暴力算法的時間復雜度O(n2)降低到O(n)。
1.2 對撞指針
實現(xiàn)步驟：
（1）left指針指向第一個元素，right指針指向最后一個元素；
（2）循環(huán)體中，滿足條件A，left指針右移；滿足條件B，right指針左移；
（3）直到left==right，即相撞時，或其他條件，跳出循環(huán)體。
試用范圍：
查找有序數(shù)組中滿足某些約束條件的一組元素：如二分查找/數(shù)字之和等問題；
字符串反轉問題，如反轉字符串、回文數(shù)、顛倒二進制等問題。
示例習題1：0167 兩數(shù)之和II - 輸入有序數(shù)組 *
題目描述：給一個已按照非遞減順序排列的整數(shù)數(shù)組numbers，從數(shù)組中找出兩個數(shù)滿足相加之和等于目標數(shù)target。函數(shù)應該以長度為2的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標值。numbers的下標從1開始計數(shù)，所以答案數(shù)組應當滿足1<=answer[0]<answer[1]<=numbers.length?？杉僭O每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。 樣例1：輸入為numbers=[2, 7, 11, 15]，target=9，輸出為[2, 7]； 樣例2：輸入為numbers=[2, 3, 4]，target=6，輸出為[1, 3]； 樣例3：輸入為numbers=[-1, 0]，target=-1，輸出為[1, 2]。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left+1, right+1]
elif total < target:
left += 1
else:
right -= 1
return [-1, -1]
示例習題2：0125 驗證回文串 *
題目描述：給定一個字符串，判斷是否為回文串（只考慮字符串中的字母和數(shù)字字符，且忽略字母的大小寫）?；匚拇刚x和反讀是一樣的。 樣例1：輸入為“A man, a plan, a canal: Panama"，輸出為true； 樣例2：輸入為“race a car”， 輸出為false。
解題思路：left指針 == right指針，相等則left+1, right-1，否則返回false。
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
示例習題3：0011 盛最多水的容器 **
題目描述：給定n個非負整數(shù)a1, a2, a3, ..., an, 每個數(shù)代表坐標中的一個點(i, ai)。在坐標內(nèi)畫n條垂直線，垂直線i的兩個端點分別為(i, ai)和(i, 0)。要求找出其中的兩條垂直線，使得它們與x軸共同構成的容器可以容納最多的水。 樣例1：輸入為[1, 8, 6, 2, 5, 4, 8, 3, 7]，輸出為49。
解題思路：水量的大小直接受兩條線中較低的那條（比較left和right的高度），循環(huán)體內(nèi)計算面積值時，同時維護更新最大面積值。
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
ans = 0
while left <= right:
area = min(height[left], height[right]) * (right - left)
ans = max(ans, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return ans
1.4 快慢指針
快慢指針指的是兩個指針從同一側開始遍歷，但移動步長一個快(fast)一個慢(slow)，停止的條件可以是快指針移動到數(shù)組尾端，也可以是兩個指針相交，也可以是滿足其他特殊條件。
實現(xiàn)步驟：
（1）slow一般指向第一個元素，即slow=0；fast一般指向第二個元素，即fast=1；
（2）循環(huán)體內(nèi)，滿足條件A，slow+1，滿足條件B或者無條件，fast+1；
（3）結束條件，停止循環(huán)。
適用范圍：
- 一般用于處理數(shù)組的移動、刪除元素等問題，或者鏈表中的判斷是否有環(huán)、長度問題。
示例習題1：0026 刪除有序數(shù)組中的重復項 *
題目描述：給一個有序數(shù)組nums，原地刪除重復出現(xiàn)的元素，使每個元素只出現(xiàn)一次，返回刪除后數(shù)組的新長度。 樣例1：輸入為nums=[1, 1, 2]，輸出為2，nums=[1, 2]； 樣例2：輸入為nums=[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]，輸出為5，nums=[0, 1, 2, 3, 4]。
解題思路：slow表示去除重復元素后的數(shù)組的末尾位置，slow=0，fast指向當前元素， fast=1。比較slow和fast上的元素是否相等，如果不等，則slow后移動1位，fast指向的元素復制到slow位置上，fast右移一位。重復，直到fast等于數(shù)組長度，返回slow+1即為新數(shù)組的長度。
class Solution:
def removeDuplicates(self, nums= List[int]) -> int:
if len(nums) <= 1:
return len(nums)
slow, fast = 0, 1
while fast < len(nums):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1
1.5 分離雙指針
實現(xiàn)步驟：
（1）left_1指向第一個數(shù)組的第一個元素，left2指向第二個數(shù)組的第一個元素；
（2）滿足條件A，left_1 + 1， left_2 + 1;
（3）滿足條件B，left_1 + 1;
（4）滿足條件C，left_2 + 1；
（5）遍歷結束一個數(shù)組或其他條件，結束循環(huán)。
適用范圍：
- 一般用于處理有序數(shù)組合并，求交集、并集問題。
示例習題1：0349 兩個數(shù)組的交集 *
題目描述：給定兩個數(shù)組，編寫函數(shù)實現(xiàn)計算它們的交集。 樣例1：輸入為nums1=[1, 2, 2, 1]，nums2=[2, 2]，輸出為[2]； 樣例2：輸入為nums1=[4, 9, 5]， nums2=[9, 4, 9, 8, 4]，輸出為[9, 4]。
解題思路：排序；left_1=0， left_2=0；當相等時，去重并加入輸出答案數(shù)組，left_1+1，left_2+1；left_1<left_2，則left_1+1；left_1>left_2，則left_2+1；輸出。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
left_1 = 0
left_2 = 0
res = []
while left_1 < len(nums1) and left_2 < len(nums2):
if nums1[left_1] == nums2[left_2]:
if nums1[left_1] not in res:
res.append(nums1[left_1])
left_1 += 1
left_2 += 1
elif nums1[left_1] < nums2[left_2]:
left_1 += 1
elif nums1[left_1] > nums2[left_2]:
left_2 += 1
return res
2 練習題目
2.1 0344 反轉字符串 *
題目描述：將輸入的字符串反轉。 樣例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"]。
解題思路： 交換前后的字符。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2.2 0015 三數(shù)之和 **
題目描述：給一個包含n個整數(shù)的數(shù)組nums，判斷nums中是否存在三個元素a, b, c，使得a+b+c=0，找出所有和為0且不重復的三元組。 樣例1：輸入為nums=[-1, 0, 1, 2, -1, -4]，輸出為[[-1, -1, 2], [-1, 0, 1]]； 樣例2：輸入為nums=[]，輸出為[]； 樣例3：輸入為nums=[0]，輸出為[]。
解題思路：沒有想明白。待填空。
2.3 0080 刪除有序數(shù)組中的重復項 II **
題目描述：與0026類似，但允許每個元素最多出現(xiàn)兩次。 樣例1：輸入為nums = [1,1,1,2,2,3]，輸出為5, nums = [1,1,2,2,3]； 樣例2：輸入為nums = [0,0,1,1,1,1,2,3,3]，輸出為7, nums = [0,0,1,1,2,3,3]。
解題思路：數(shù)量進行了限制，比較的時候需要加上前一項。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
slow = 2
fast = 2
while fast < len(nums):
if nums[slow - 2] != nums[fast]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
2.4 0283 移動零 *
題目描述：給定一個數(shù)組nums，將所有0移動到數(shù)組的末尾，同時保持非零元素的相對順序。 樣例1：輸入為[0, 1, 0, 3, 12]，輸出為[1, 3, 12, 0, 0]。
解題思路：左指針左邊都為非零數(shù)，左指針到右指針間都為0。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
時間復雜度：O(n)；空間復雜度：O(1)。
