Leetcode（双指针习题思路总结，持续更新。。。）

讲解题目：两数之和

给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[0,1]

双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中

我们需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了

def twoSum(numbers, target):
    ans = []
    p1 = 0
    p2 = len(numbers) - 1
    while p2 > p1:
        array_sum = numbers[p1] + numbers[p2]
        if array_sum == target:
            ans.append(p1)
            ans.append(p2)
            break
        if array_sum > target:
            p2 -= 1
        else:
            p1 += 1
    return ans

习题1

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

def removeDuplicates(nums):
    p1, p2 = 0, 0
    while p2 < len(nums):

        if nums[p2] != nums[p1]:
            nums[p1 + 1] = nums[p2]
            p1 += 1

        p2 += 1
    return p1 + 1

习题2

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

def sortedSquares(nums):
    p1 = 0
    p2 = len(nums) - 1
    ans = []
    while p2 >= 0 and p1 < len(nums) and p1 <= p2:
        if abs(nums[p1]) < abs(nums[p2]):
            ans.append(nums[p2] ** 2)
            p2 -= 1
        else:
            ans.append(nums[p1] ** 2)
            p1 += 1
    return ans[::-1]

习题3

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

def moveZeroes(nums):
    p1 = 0
    p2 = 0
    while p1 < len(nums) and p2 < len(nums):
        if nums[p2] != 0:
            nums[p1], nums[p2] = nums[p2], nums[p1]
            p1 += 1
        p2 += 1
    return nums

习题4

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

示例
输入：[1,8,6,2,5,4,8,3,7]
输出：49

def maxArea(height):
    max_area = 0
    start, end = 0, len(height) - 1
    
    while start <= end:
        x = end - start
        y = min(height[start], height[end])
        max_area = max(x * y, max_area)
        if height[start] < height[end]:
            start += 1
        else:
            end -= 1
    return max_area

原文地址：https://blog.csdn.net/weixin_43336108/article/details/144029135

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！