第11-12天打卡，附上学习链接
1 学习内容
1.1 双指针（Two Pointers）
双指针指的是在遍历元素的过程中，使用两个指针，方向相反称之为对撞指针，方向相同则称之快慢指针，如果属于不同的数组/链表，则称之为分离双指针。在数组的区间问题上，双指针可以将暴力算法的时间复杂度O(n2)降低到O(n)。
1.2 对撞指针
实现步骤：
（1）left指针指向第一个元素，right指针指向最后一个元素；
（2）循环体中，满足条件A，left指针右移；满足条件B，right指针左移；
（3）直到left==right，即相撞时，或其他条件，跳出循环体。
试用范围：
查找有序数组中满足某些约束条件的一组元素：如二分查找/数字之和等问题；
字符串反转问题，如反转字符串、回文数、颠倒二进制等问题。
示例习题1：0167 两数之和II - 输入有序数组 *
题目描述：给一个已按照非递减顺序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。函数应该以长度为2的整数数组的形式返回这两个数的下标值。numbers的下标从1开始计数，所以答案数组应当满足1<=answer[0]<answer[1]<=numbers.length。可假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 样例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 验证回文串 *
题目描述：给定一个字符串，判断是否为回文串（只考虑字符串中的字母和数字字符，且忽略字母的大小写）。回文串指正读和反读是一样的。 样例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个非负整数a1, a2, a3, ..., an, 每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0)。要求找出其中的两条垂直线，使得它们与x轴共同构成的容器可以容纳最多的水。 样例1：输入为[1, 8, 6, 2, 5, 4, 8, 3, 7]，输出为49。
解题思路：水量的大小直接受两条线中较低的那条（比较left和right的高度），循环体内计算面积值时，同时维护更新最大面积值。
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)，停止的条件可以是快指针移动到数组尾端，也可以是两个指针相交，也可以是满足其他特殊条件。
实现步骤：
（1）slow一般指向第一个元素，即slow=0；fast一般指向第二个元素，即fast=1；
（2）循环体内，满足条件A，slow+1，满足条件B或者无条件，fast+1；
（3）结束条件，停止循环。
适用范围：
- 一般用于处理数组的移动、删除元素等问题，或者链表中的判断是否有环、长度问题。
示例习题1：0026 删除有序数组中的重复项 *
题目描述：给一个有序数组nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。 样例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表示去除重复元素后的数组的末尾位置，slow=0，fast指向当前元素， fast=1。比较slow和fast上的元素是否相等，如果不等，则slow后移动1位，fast指向的元素复制到slow位置上，fast右移一位。重复，直到fast等于数组长度，返回slow+1即为新数组的长度。
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 分离双指针
实现步骤：
（1）left_1指向第一个数组的第一个元素，left2指向第二个数组的第一个元素；
（2）满足条件A，left_1 + 1， left_2 + 1;
（3）满足条件B，left_1 + 1;
（4）满足条件C，left_2 + 1；
（5）遍历结束一个数组或其他条件，结束循环。
适用范围：
- 一般用于处理有序数组合并，求交集、并集问题。
示例习题1：0349 两个数组的交集 *
题目描述：给定两个数组，编写函数实现计算它们的交集。 样例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；当相等时，去重并加入输出答案数组，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 三数之和 **
题目描述：给一个包含n个整数的数组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 删除有序数组中的重复项 II **
题目描述：与0026类似，但允许每个元素最多出现两次。 样例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]。
解题思路：数量进行了限制，比较的时候需要加上前一项。
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 移动零 *
题目描述：给定一个数组nums，将所有0移动到数组的末尾，同时保持非零元素的相对顺序。 样例1：输入为[0, 1, 0, 3, 12]，输出为[1, 3, 12, 0, 0]。
解题思路：左指针左边都为非零数，左指针到右指针间都为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)。
