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 = 0p2 = len(numbers) - 1while p2 > p1:array_sum = numbers[p1] + numbers[p2]if array_sum == target:ans.append(p1)ans.append(p2)breakif array_sum > target:p2 -= 1else:p1 += 1return 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, 0while p2 < len(nums):if nums[p2] != nums[p1]:nums[p1 + 1] = nums[p2]p1 += 1p2 += 1return 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 = 0p2 = len(nums) - 1ans = []while p2 >= 0 and p1 < len(nums) and p1 <= p2:if abs(nums[p1]) < abs(nums[p2]):ans.append(nums[p2] ** 2)p2 -= 1else:ans.append(nums[p1] ** 2)p1 += 1return 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 = 0p2 = 0while p1 < len(nums) and p2 < len(nums):if nums[p2] != 0:nums[p1], nums[p2] = nums[p2], nums[p1]p1 += 1p2 += 1return 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 = 0start, end = 0, len(height) - 1while start <= end:x = end - starty = min(height[start], height[end])max_area = max(x * y, max_area)if height[start] < height[end]:start += 1else:end -= 1return 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]:continuep1, p2 = i + 1, len(nums) - 1while p1 < p2:if p1 > i + 1 and nums[p1] == nums[p1 - 1]:p1 += 1continueif nums[p1] + nums[p2] == 0 - nums[i]:ans.append([nums[i], nums[p1], nums[p2]])p1 += 1elif nums[p1] + nums[p2] > 0 - nums[i]:p2 -= 1else:p1 += 1return ans