Leetcode(双指针习题思路总结,持续更新。。。)

发布于:2024-11-28 ⋅ 阅读:(50) ⋅ 点赞:(0)

 讲解题目:两数之和

给定一个已按照 升序排列  的整数数组 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

习题5

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
def threeSum(nums):
    ans = []
    
    nums = sorted(nums)
    for i in range(len(nums)):

        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        p1, p2 = i + 1, len(nums) - 1
        while p1 < p2:
            if p1 > i + 1 and nums[p1] == nums[p1 - 1]:
                p1 += 1
                continue
            if nums[p1] + nums[p2] == 0 - nums[i]:
                ans.append([nums[i], nums[p1], nums[p2]])
                p1 += 1
            elif nums[p1] + nums[p2] > 0 - nums[i]:
                p2 -= 1
            else:
                p1 += 1
    
    return ans