双指针

11、盛水最多的容器

我们使用双指针的思想，两个指针分别为数组的头尾结点，每轮都进行面积的计算，并且每轮只移动较小结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left = 0    # 左指针
        right = n - 1   # 右指针
        max_s = 0   # 面积最大值
        s = 0   # 面积
        l = 0   # 边长
        while right > left:
            if height[left] > height[right]:
                l = height[right]
            else:
                l = height[left]
            s = (right - left) * l
            if s > max_s:
                max_s = s
            if height[left] > height[right]:
                right = right - 1
            else:
                left = left + 1
        return max_s

15、三数之和

采用双指针的思想，为了不使三元组重复，先对数组进行排序。当确定了第一个元素，只需要对剩下元素进行设置左指针和右指针，如果三元组大与0，右指针就左移一位，反之亦然。如果三元组之和刚好等于0，就需要左指针和右指针都移动一位。这时候还会出现重复问题，所以需要判断此时遍历的元素和之前的是否相同，如果相同就要跳过。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = list()
        for i in range(n):	# 固定其中一个元素
            if i == 0 or nums[i] != nums[i - 1]:
                k = n - 1
                j = i + 1
                while k > j:	# 进行双指针遍历
                    if k != n - 1 and nums[k] == nums[k + 1]:	# 如果右指针之前出现过就跳过
                        k = k - 1
                        continue
                    if j != i + 1 and nums[j] == nums[j - 1]:	# 如果左指针之前出现过就跳过
                        j = j + 1
                        continue
                    s = nums[i] + nums[j] + nums[k]
                    if s == 0:
                        ans.append([nums[i], nums[j], nums[k]])
                        k = k - 1
                        j = j + 1
                    elif s > 0:
                        k = k - 1
                    elif s < 0:
                        j = j + 1
        return ans

16、最接近的三数之和

采用双指针的思想，先对数组进行排序。当确定了第一个元素，只需要对剩下元素进行设置左指针和右指针，如果三元组之和大于target，我们只需要将右节点左移一位，相反亦然。

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
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        min_num = 10**9
        ans = 0
        for i in range(n):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            k = n - 1
            j = i + 1
            while k > j:
                s = nums[i] + nums[j] + nums[k]
                if s == target:
                    return s
                if s > target:
                    if s - target < min_num:
                        min_num = s - target
                        ans = s
                    k = k - 1
                elif s < target:
                    if target - s < min_num:
                        min_num = target - s
                        ans = s
                    j = j + 1
        return ans

18、四数之和

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
36
37
38
39
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if nums == [] or n < 4:
            return []
        nums.sort()
        ans = list()
        for i in range(n - 3):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                continue
            for j in range(i + 1, n - 2):
                if j != i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                    continue
                k = j + 1
                l = n - 1
                while k < l:
                    sum = nums[i] + nums[j] + nums[k] + nums[l]
                    if sum < target:
                        k = k + 1
                    elif sum > target:
                        l = l - 1
                    elif sum == target:
                        ans.append([nums[i], nums[j], nums[k], nums[l]])
                        while k < l and nums[k] == nums[k + 1]:
                            k = k + 1
                        k = k + 1
                        while k < l and nums[l] == nums[l - 1]:
                            l = l - 1
                        l = l - 1 

        return ans

19、删除链表的倒数第N个结点

采用双指针的思想，左右指针都为指向头节点，首先右指针向后遍历n个结点，最后让左右一起向后遍历直至右指针指向的为最后一个结点，这时候左指针指向的就是倒数第n个结点的前一个结点，就可以进行删除的操作了。

但是有一个特殊情况，如果删除的是头结点，上述不成立，所以要单独进行一个if判断，如果右指针向后遍历n个结点后为空，那么删除的就是头结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        right = head
        left = head
        for i in range(n):
            right = right.next
        if right == None:	# 如果要删除的是头结点
            left = left.next
            return left
        while right.next != None:
            left = left.next
            right = right.next
        left.next = left.next.next
        return head

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        n = len(nums)
        left, right = 1, 1
        while right < n:
            if nums[right] != nums[right - 1]:
                nums[left] = nums[right]
                left = left + 1
            right = right + 1
        return left

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

因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。

如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元 素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        l, r = 0, n - 1
        while l < r:
            if numbers[l] + numbers[r] == target:
                res = [l + 1, r + 1]
                break
            elif numbers[l] + numbers[r] < target:
                l += 1
            elif numbers[l] + numbers[r] > target:
                r -= 1
        return res

88、 合并两个有序数组

因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。 因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。

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
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 i >= 0 and j >= 0:
            if nums1[i] >= nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
                k -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
                k -= 1
        if i >= 0:
            while i >= 0:
                nums1[k] = nums1[i]
                i -= 1
                k -= 1
        if j >= 0:
            while j >= 0:
                nums1[k] = nums2[j]
                j -= 1
                k -= 1

142、环形链表

对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存 在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while True:
            if not fast or not fast.next:
                return
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        fast = head
        while True:
            if slow == fast:
                return fast
            slow = slow.next
            fast = fast.next

76、最小覆盖子串

本题使用滑动窗口求解，即两个指针 start 和 end 都是从最左端向最右端移动，且 start 的位置一定在 end 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移动 start 指针，且 start 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。本题使用了t_disk字典代表t中各个字符的数量，window_disk字典代表目前左右指针指向的子串中各个字符的数量。

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
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        t_disk, window_disk = {}, {}
        for i in range(len(t)):
            if t[i] in t_disk:
                t_disk[t[i]] += 1
            else:
                t_disk[t[i]] = 1
        
        for key in t_disk:
            window_disk[key] = 0

        start, res, min_len = 0, '', float('inf')

        for end in range(len(s)):
            if s[end] in window_disk:
                window_disk[s[end]] += 1
            else:
                window_disk[s[end]] = 1

            while self.check_windows(t_disk, window_disk):
                if min_len > end - start + 1:
                    min_len = end - start + 1
                    res = s[start: end + 1]
                window_disk[s[start]] -= 1
                start += 1

        return res

    def check_windows(self, s, t):
        for key in s:
            if s[key] > t[key]:
                return False
        return True
LeetCode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！