LeetCode题目总结-数组中的双指针问题

发表于 | 分类于 ， | 评论数： | 阅读次数：
本文字数： 19k | 阅读时长 ≈ 18 分钟

所谓双指针算法，就是指的是在遍历的过程中，不是普通的使用单个指针进行循环访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算，降低时间复杂度.

本文主要总结了几种双指针算法在数组类题目中的应用，下面是目录：

对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

1-两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

思路

我们马上可以想到一个暴力解法：遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。但是这个方法时间复杂度达到O(n^2)。

因此，我想到用哈希表以空间换取速度，将查找时间从 O(n) 降低到 O(1)。

在进行迭代并将元素插入到哈希表的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

注意：这里没有使用对撞指针，因为这里数组是无序的，而排序的时间复杂度为O(nlogn)，所以不太划算。

Python实现

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums, target):
        nums_dict = {}
        for i in range(len(nums)):
            temp = target - nums[i]
            if temp in nums_dict:
                return [i,nums_dict[temp]]
            else:
                nums_dict[nums[i]] = i
  • 时间复杂度：O(n)，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
  • 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

15-三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：

1
2
3
4
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

这里思路来源于167- 两数之和 II - 输入有序数组。我们可以先对数组进行排序，然后我们选择一个数字做C位，然后我们在这个C位数字的右边进行双指针搜索：

  • 从最左边i+1（最小值）和最右边len(nums)-1（最大值）两个数字开始，加上C位，计算总和是否等于0。
    • 如果大于 0，说明实力太强了，就把右侧的数字左移一位。
    • 如果小于 0，说明实力太弱了，就把左边的数字右移一位。
  • 当双指针碰到的时候，这轮循环结束，以该数字为C位的所有可能都已经尝试完毕了。

这里要注意数组的去重，去重过程包含了遍历，也会增加时间复杂度，所以我进行了优化，对于排序完成的数组来说，只要判断下相邻的数是否相等，如果相等就直接移动指针即可，这就完成了去重。

Python实现

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
class Solution:
    def threeSum(self,nums):
        # 排序
        nums.sort()

        # 单循环+双指针
        res = []

        for i in range(len(nums)):
            # 去重（如果当前C位数和相邻的数相等，直接移动指针）
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                elif nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i],nums[left],nums[right]])

                    # 去重（如果当前数和相邻的数相等，直接移动指针）
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    
                    left += 1
                    right -= 1

        return res
  • 时间复杂度：O(n^2)

16-最接近的三数之和

问题描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
3
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

思路

这个题目跟15-三数之和类似，只是需要保存一下最接近target的值，搜索过程中碰到更接近的数就更新这个值。

具体步骤如下：

  1. 在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]。
  2. 使用前指针指向 left = i + 1 处，后指针指向 right = len(nums) - 1 处，也就是结尾处，根据 sums = nums[i] + nums[left] + nums[right] 的结果，判断 sums 与目标 target 的距离，如果更近则更新结果a。
  3. 因为数组有序，如果 sums > target 则 right -= 1，如果 sums < target 则 left += 1，如果 sums == target 则说明距离为 0，直接返回结果。

Python实现

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
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 排序
        nums.sort()

        # 初始化
        a = abs(nums[0] + nums[1] + nums[2] - target)
        res = nums[0] + nums[1] + nums[2]

        for i in range(len(nums)):
            left = i + 1
            right = len(nums) - 1

            # 当前nums[i]情况下，搜索最接近的组合
            while left < right:
                sums = nums[i] + nums[left] + nums[right]
                # 比较sums与目标target的距离与之前最近的距离，如果更近则更新
                if abs(sums-target) < a:
                    a = abs(sums-target)
                    res = sums
                
                if sums > target:
                    right -= 1
                elif sums < target:
                    left += 1
                # 如果sums == target，则说明距离为0，这就是最接近的数
                elif sums == target:
                    return sums
        return res

18-四数之和

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

思路

这道题目跟15.三数之和基本类似，也可以采用对撞指针进行解决，只是外面多了一个循环。

其中的难点在于四元组的去重。

最简单的办法是在结果列表中进行查找判断是否有重复的四元组，如果没有再存入，但是效率比较低，这里我采用如果当前值等于之前的值，那么我就跳过这个数来去重。

Python实现

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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 排序
        nums.sort()

        res = []

        for i in range(len(nums)-3):
            # 去重：确保nums[i]改变了
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            for j in range(i+1,len(nums)-2):
                # 去重：确保nums[j]改变了
                if j > i+1 and nums[j] == nums[j-1]:
                    continue                

                left = j + 1
                right = len(nums) - 1

                while left < right:
                    sums = nums[i] + nums[j] + nums[left] + nums[right]
                    if sums == target:
                        res.append([nums[i],nums[j],nums[left],nums[right]])
                        # 去重：确保nums[left]改变了
                        while left < right and nums[left] == nums[left+1]:
                            left += 1
                        # 去重：确保nums[right]改变了
                        while left < right and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif sums < target:
                        left += 1
                    elif sums > target:
                        right -= 1
        
        return res
  • 时间复杂度：O(n^3)

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

问题描述

给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

  • 返回的下标值（index1 和 index2）不是从零开始的。
  • 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

  • 输入: numbers = [2, 7, 11, 15], target = 9
  • 输出: [1,2]
  • 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

思路

我们可以使用 两数之和 的解法在 O(n^2) 时间 O(1) 空间暴力解决，也可以用哈希表在 O(n) 时间和 O(n) 空间内解决。然而，这两种方法都没有用到输入数组已经排序的性质，我们可以做得更好。

我们使用两个指针，初始分别位于第一个元素和最后一个元素位置，比较这两个元素之和与目标值的大小。如果和等于目标值，我们发现了这个唯一解。如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一。移动指针后重复上述比较直到找到答案。

Python实现

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def twoSum(self, numbers, target):
        i = 0
        j = len(numbers)-1
        while True:
            if numbers[i] + numbers[j] > target:
                j -= 1
            elif numbers[i] + numbers[j] < target:
                i += 1
            elif numbers[i] + numbers[j] == target:
                return [i+1,j+1]

11-盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

1
2
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

思路

这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

下面我们从公式来验证上面的结论：

  • 水槽面积公式：S(i,j)=min(h[i],h[j])×(j−i)
    • 若向内移动短板，水槽的短板 min(h[i], h[j]) 可能变大，因此水槽面积 S(i,j) 可能增大。
    • 若向内移动长板，水槽的短板 min(h[i], h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。

我们也会发现：若不指定移动规则，所有移动出现的 S(i,j) 的状态数为 C(n,2)，即暴力枚举出所有状态。在状态 S(i,j) 下向内移动短板至 S(i+1,j)（假设 h[i] < h[j]），则相当于消去了 S(i,j−1),S(i,j−2),...,S(i,i+1) 状态集合。而所有消去状态的面积一定 <=S(i,j)。

Python实现

具体步骤如下：

我们在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。 此外，我们会使用变量 maxarea 来持续存储到目前为止所获得的最大面积。 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 maxarea，并将指向较短线段的指针向较长线段那端移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        # 初始值
        res = min(height[left],height[right]) * (len(height) - 1)

        while left < right:
            # 更新maxarea
            if min(height[left],height[right]) * (right - left) > res:
                res = min(height[left],height[right]) * (right - left)

            # 移动较短线段的指针
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return res

611-有效三角形的个数

题目描述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

1
2
3
4
5
6
7
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  • 数组长度不超过1000。
  • 数组里整数的范围为 [0, 1000]。

思路

三角形的性质：三角形的任何两边的和一定大于第三边，由此亦可证明得三角形的任意两边的差一定小于第三边。

根据三角形的性质，我们会发现，只要小的两个边之和大于最长的那个边（a + b > c），任意两边就一定大于第三边。

  1. 数组排序，便于后序的处理
  2. 固定最长的边c，然后采用双指针在其左侧寻找合适的a、b：
    • a从最左侧开始（nums[0]）、b从最右侧开始（nums[i-1]）
    • 如果nums[left] + nums[right] > nums[i]，说明[left,right]、[left+1,right]...[right-1,right]均满足条件，以nums[right]为中间边的情况已全部考虑过，然后right -= 1
    • 如果nums[left] + nums[right] <= nums[i]，两边之和太小，需要增大，left += 1

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        # 排序
        nums.sort()

        count = 0
        for i in range(2,len(nums)):
            
            left = 0
            right = i - 1

            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    # 这些都可以：[left,right]、[left+1,right]...[right-1,right]
                    count += right - left
                    right -= 1
                else:
                    left += 1
        
        return count
  • 时间复杂度：O(n^2)

前向型指针-快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

不少链表的题目可以用快慢指针来解决，由于本文主要双指针在数组中的应用，这里就不讨论了。

26-删除排序数组中的重复项

问题描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 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。你不需要考虑数组中超出新长度后面的元素。

说明:为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

思路

数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

当我们遇到 nums[j] != nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。

图解：

来源：【双指针】删除重复项-带优化思路

Python实现

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

27-移除元素

问题描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

  • 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
  • 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

思路

我们可以保留两个指针 i 和 j，其中 i 是慢指针，j 是快指针。当 nums[j] 与给定的值相等时，递增 j 以跳过该元素。只要 nums[j] != val，我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        j = 0
        while j < len(nums):
            if nums[j] == val:
                j += 1
            elif nums[j] != val:
                nums[i] = nums[j]
                i += 1
                j += 1
        return i
  • 时间复杂度：O(n)，假设数组总共有 n 个元素，i 和 j 至少遍历 2n 步。
  • 空间复杂度：O(1)。

进阶做法

现在考虑数组包含很少的要删除的元素的情况。例如， num=[4，1，2，3，5]，Val=4。似乎没有必要将 [1，2，3，5] 这几个元素左移一步，因为问题描述中提到元素的顺序可以更改。当我们遇到 nums[i] = val 时，我们可以将当前元素与最后一个元素进行交换，并释放最后一个元素。这实际上使数组的大小减少了 1。请注意，被交换的最后一个元素可能是您想要移除的值。但是不要担心，在下一次迭代中，我们仍然会检查这个元素。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        j = 0
        last = len(nums)-1
        while j <= last:
            if nums[j] == val:
                nums[j] = nums[last]
                last -= 1
            else:
                j += 1
        return last+1

注意：while循环中的判断条件应该是j <= last而不是j < len(nums)。

  • 时间复杂度：O(n)，j 和 last 最多遍历 n 步。在这个方法中，赋值操作的次数等于要删除的元素的数量。因此，如果要移除的元素很少，效率会更高。
  • 空间复杂度：O(1)。

80-删除排序数组中的重复项

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。你不需要考虑数组中超出新长度后面的元素。

思路

遍历整个表：

  • 把当前的元素与它前面的对比，如果二者元素相同（为重复元素）：此时统计重复的计数器count+=1。题目要求只保留2个重复的元素，这里需要加入重复元素个数的判断：

    • 这个元素正好重复了2次 => 则进行保留。列表长度i+=1，然后nums[i]=nums[j]；
    • 这个元素重复多于2次 => 不进行任何操作。体现在程序上不做处理

  • 把当前的元素与它前面的对比，如果二者元素不同（为新元素）：此时把当前这个结点(nums[j])添加到新表里面去，nums[i] = nums[j],表长i+1。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 1
        i = 0
        j = 1
        while j < len(nums):
            # 二者元素相同（重复元素）
            if nums[i] == nums[j]:
                count += 1
                # 这个元素正好重复了2次
                if count == 2:
                    i += 1
                    nums[i] = nums[j]
                # 这个元素重复多于2次
                else:
                    pass
                j += 1
            # 二者元素不同（新元素）
            else:
                i += 1
                nums[i] = nums[j]
                count = 1
                j += 1
        return i+1

283-移动零

问题描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

  • 输入: [0,1,0,3,12]
  • 输出: [1,3,12,0,0]

说明:

  • 必须在原数组上操作，不能拷贝额外的数组。
  • 尽量减少操作次数。

思路

  1. nums中，i指针用于存放非零元素
  2. j指针用于遍历寻找非零元素（注：j指针找到一个非零元素后，方法nums[i]的位置i++，用于下一个j指针找到的非零元素）
  3. j指针遍历完后，最后nums数组还有空位置，存放0即可

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        j = 0
        # 双指针遍历寻找非零元素
        while j < len(nums):
            if nums[j] == 0:
                j += 1
            else:
                nums[i] = nums[j]
                i += 1
                j += 1
        
        # 空位置赋0
        for k in range(i,len(nums)):
            nums[k] = 0

845-数组中的最长山脉

题目描述

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

  • B.length >= 3
  • 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

注意：B 可以是 A 的任意子数组，包括整个数组 A。

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

1
2
3
输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

1
2
3
输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

  • 0 <= A.length <= 10000
  • 0 <= A[i] <= 10000

思路

首先固定山峰值，然后分别寻找左、右半边山脉的长度。

  • A[left] < A[left+1]，继续向左寻找
  • A[right] < A[right-1]，继续向右寻找

如果以当前山峰的山脉长度比最长山脉长，更新最长山脉。

注意：我们可以在只有当前点为山峰的情况（即A[i-1] < A[i] and A[i+1] < A[i]），才在左右寻找最长山峰，这样可以大大降低搜索的次数。

Python实现

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 longestMountain(self, A: List[int]) -> int:
        if len(A) < 3:
            return 0
        
        res = 0

        # 固定山峰
        for i in range(1,len(A)-1):
            # 只有当前点为山峰的情况，才在左右寻找最长山峰
            if A[i-1] < A[i] and A[i+1] < A[i]:
                left = i - 1
                right = i + 1

                # 左半边山脉的长度
                while left >= 0 and A[left] < A[left+1]:
                    left -= 1

                # 右半边山脉的长度
                while right <= len(A)-1 and A[right] < A[right-1]:
                    right += 1

                # 如果这个山脉比最长的山脉长，更新res
                if right - left - 1 > res:
                    res =  right - left - 1
        
        return res

前向型指针-滑动窗口

有些时候，我们需要获得数组或者字符串的连续子部分，这时候我们就可以考虑使用滑动窗口。nums[left,right]为滑动窗口，根据具体的要求，通过遍历的时候，来改变left和right的位置，从而完成任务。

由于本文主要关注双指针在数组中的应用，这里就不讨论字符串相关的题目了。

209-长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

1
2
3
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

思路

在一个坐标上存在两个指针left和right，left代表滑窗的左边框，right代表滑窗的右边框。两者分别向右滑动，前者能使窗口之间的和减小，后者能使窗口之间的和增大。开始时二者重合，窗口的和就是重合点所在的数。

  1. 开始right向右滑动，使和变大。
  2. 当恰好>=s时，记录滑窗所包括的子数组长度res，若res已有数值，需判断新值是否小于旧值，若是，更新res；left向右滑动。
  3. 判断是否仍>=s，若是，重复步骤2，3。若否，转步骤1。直到右边框到达最右边。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # 初始化
        left,sums,res = 0,0,float('inf')

        # 右指针右移
        for right in range(len(nums)):
            sums += nums[right]
            while sums >= s:
                # 若新值小于旧值，更新res
                if right - left + 1 < res:
                    res = right - left + 1
                # 左指针向右滑动
                sums -= nums[left]
                left += 1

        return 0 if res == float('inf') else res
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

713-乘积小于K的子数组

题目描述

给定一个正整数数组 nums。

找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

1
2
3
4
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

说明:

  • 0 < nums.length <= 50000
  • 0 < nums[i] < 1000
  • 0 <= k < 10^6

思路

  • 步骤1：当left <= right且滑动窗口内的乘积小于k时，我们可以知道[left,right]、[left+1,right]...[right-1,right]均满足条件，因此，计数加right-left+1，然后移动右边界（滑动区间加大），看剩下的区间是否满足乘积小于k，如果小于k，重复步骤1，否则进行步骤2。
  • 步骤2：当滑动窗口内的乘积大于等于k时，右移左边界（滑动区间减小），如果这个区间内乘积小于k，进入步骤1，否则重复步骤2。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:        
        left = 0
        product = 1
        count = 0
        for right in range(len(nums)):
            # 右边界右移
            product *= nums[right]
            # 如果乘积>=k，左边界右移
            while left <= right and product >= k:
                product /= nums[left]
                left += 1
            # 当前右边界下，满足条件的数组
            count += right - left + 1
        return count

分离双指针

输入是两个数组/链表，两个指针分别在两个容器中移动；根据问题的不同，初始位置可能都在头部，或者都在尾部，或一头一尾。

349-两个数组的交集

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

思路

我先对两个数组进行排序。然后再运用双指针遍历两个数组，将交集中的元素加入到 set() 中。set() 可以非常方便的去重。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 排序
        nums1.sort()
        nums2.sort()

        i,j = 0,0
        nums_set = set()
        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] == nums2[j]:
                nums_set.add(nums1[i])
                i += 1
                j += 1
        
        return nums_set

其他方法——运用set()的方法

我们可以将两个数组转换为集合 set，然后直接用内置的交集即可得到结果。

1
2
3
4
5
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return set1 & set2
  • 时间复杂度：O(m+n)，其中 n 和 m 是数组的长度。O(n) 的时间用于转换 nums1 在集合中，O(m) 的时间用于转换 nums2 到集合中，并且平均情况下，集合的操作为 O(1)。
  • 空间复杂度：O(m+n)，最坏的情况是数组中的所有元素都不同。

350-两个数组的交集

题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

思路

我先对两个数组进行排序。然后再运用双指针遍历两个数组，将交集中的元素加入到 列表 中。

本题跟349. 两个数组的交集的区别在于，本题不需要去重，因此用列表而不是集合保存结果。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 排序
        nums1.sort()
        nums2.sort()

        i,j = 0,0
        res = []

        while i < len(nums1) and j < len(nums2):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
        
        return res

88-合并两个有序数组

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

思路

这个题目可以参考归并排序中的方法来解决。具体见。

推荐文章
赞赏一杯咖啡
0%