双指针

刷题

image-20240311205603588

88. 合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.
        """
        # 使用三个指针，p1,p2,p = m-1,n-1,m+n-1,比较p1和p2处的值，谁大就和p交换位置，之后p移到下一个位置
        p1,p2,p = m-1,n-1,m+n-1
        while p2>=0: # nums2数组还有元素
            if p1>=0 and nums1[p1]>nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

125. 验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 双指针方法
        s=s.lower()
        l,r = 0,len(s)-1
        while l<r:
            while l<len(s)-1 and not s[l].isalnum():
                l += 1
            while r>0 and not s[r].isalnum():
                r -= 1
            if s[l].isalnum() and s[r].isalnum():
                if s[l]!=s[r]:
                    return False
                l+=1
                r-=1
        return True

同向双指针（快慢）

283. 移动零

  • 同向快慢双指针：快指针每次循环走一步，当快指针遇到非0元素时，慢指针走一步，并且此时交换快慢指针的元素，否则慢指针不移动
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def moveZeroes(self, nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low,fast = 0,0
        while fast < len(nums):	#不超过边界
            if nums[fast] != 0:
                nums[low],nums[fast] = nums[fast],nums[low]
                low += 1
            fast += 1

26. 删除有序数组中的重复项

  • 数组非严格递增，原地删除重复元素，返回删除后的数组长度
  • 思路：快慢指针，如果nums[low] != nums[fast]则 慢指针右移一步，并交换nums[low],nums[fast] = nums[fast],nums[low]，快指针每次循环右移一步。
  • 注意：fast += 1应该写在if后面，否则会出现溢出错误
  • 最后，low指针左侧的元素为唯一项，返回数组长度low+1
1
2
3
4
5
6
7
8
9
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        low,fast = 0,0
        while fast<len(nums):           
            if nums[low] != nums[fast]:
                low += 1	# 注意先移动慢指针，再交换元素
                nums[low],nums[fast] = nums[fast],nums[low]
            fast += 1
        return low+1

27. 移除元素

1
2
3
4
5
6
7
8
9
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l,f = 0,0
        while f<len(nums):
            if nums[f]!=val:
                nums[l],nums[f] = nums[f],nums[l]	# # 注意先交换元素，再移动慢指针
                l += 1
            f += 1
        return l

相向双指针

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

  • 数组下标从1开始，所以之后返回的双指针得要+1
  • 数组非递减顺序排列
  • 每个target只对应唯一的答案
  • 空间要求O(1)
1
2
3
4
5
6
7
8
9
10
11
12
# 时间复杂度O(N)
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l,r = 0,len(numbers)-1
        while l<r:
            if numbers[l]+numbers[r]>target:
                r -= 1
            elif numbers[l] + numbers[r]<target:
                l += 1              
            else:
                return [l+1,r+1]
        return []

15. 三数之和

  • 因为题目没有说有序，先进行排序
image-20240315214820829 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 时间复杂度O(N^2)；空间复杂度O(1)
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 先进行排序
        nums.sort()
        result = [] # 存放结果

        for i in range(len(nums)-2):
            # 如果当前的元素与它左边的元素相同，就跳过
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            # 优化：当nums[i]+nums[i+1]+nums[i+2]>0，就直接返回
            if nums[i] + nums[i+1] +nums[i+2]>0:
                break
            if nums[i]+nums[-2]+ nums[-1]<0:
                continue

            l = i + 1
            r = len(nums)-1
            while l<r:
                s = nums[i]+nums[l]+nums[r]            
                if s == 0:
                    result.append([nums[i],nums[l],nums[r]])
                    while l<r and nums[r] == nums[r-1]:
                        r -= 1
                    while l<r and nums[l] == nums[l+1]:
                        l += 1
                    r -= 1
                    l += 1
                elif s> 0:
                    r -= 1
                else:
                    l += 1
        return result