15. 三数之和
16. 最靠近的三数之和
18. 四数之和
26. 删除排序数组中的反复项
27. 移除元素
75. 色彩分类
88. 合并两个有序数组
21. 合并两个有序链表
剑指 Offer 21. 调整数组程序使奇数位于偶数后面
15. 三数之和
给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不反复的三元组。
留神：答案中不能够蕴含反复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组汇合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
咱们仍然应用与两数之和相似的想法, 将三数之和转换为两数之和, 即首先须要固定第一个数, 而后去挪动其余两个数, 并且为了不便, 首先将数组进行排序.
具体思路如下
- 排序
- 固定第一个数, 用p0示意. 应用另外两个指针p1, p2, 别离指向第一个数前面的元素和最初一个元素.
- 当p0, p1, p2指向的元素之和大于0时, p2左移, 小于0时, p1右移, 否则, 将以后的3个元素增加到后果中. 当p1 = p2时, 完结循环. 回到第2步.
依照上述的思路, 能够写出如下的代码
def ThreeSum(nums): if not sums or len(sums) < 3: return [] nums.sort() n = len(nums) res = [] for i in range(n-2): p1 = i + 1 p2 = n - 1 while p1 < p2: if nums[p1] + nums[p2] < -nums[i]: p1 += 1 elif nums[p1] + nums[p2] > -nums[i]: p2 -= 1 else: res.append([nums[i], nums[p1], nums[p2]]) p1 += 1 p2 -= 1 return res额, 看上去代码并没有什么问题, 构造也还算清楚, 但其实存在一个较大的问题, 上述代码会失去反复的后果
比方一个排序数组[-4, -1, -1, 0, 1, 2]，上述代码会失去
[[-1,-1,2],[-1,0,1],[-1,0,1]]的后果, 因而咱们须要跳过第二个及当前的反复元素.
def ThreeSum(nums): if not sums or len(sums) < 3: return [] nums.sort() n = len(nums) res = [] """ 如果第一个元素就大于0或者最初一个元素还小于0间接返回. """ if nums[0] > 0 or nums[-1] < 0: return res for i in range(n-2): p1 = i + 1 p2 = n - 1 """ 去重 """ if i > 0 and nums[i] == nums[i-1]: continue while p1 < p2: if nums[p1] + nums[p2] < -nums[i]: p1 += 1 elif nums[p1] + nums[p2] > -nums[i]: p2 -= 1 else: res.append([nums[i], nums[p1], nums[p2]]) """ 去重 """ while p1 < p2 and nums[p1] == nums[p1 + 1]: p1 += 1 while p1 < p2 and nums[p2] == nums[p2 - 1]: p2 -= 1 p1 += 1 p2 -= 1 return res工夫复杂度为$O(n^2)$, 空间复杂度为$O(1)$
16. 最靠近的三数之和
给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在惟一答案。
示例：
输出：nums = [-1,2,1,-4], target = 1
输入：2
解释：与 target 最靠近的和是 2 (-1 + 2 + 1 = 2) 。
这题的思路和上一题的思路相似，同样是固定第一个数, 挪动其余两个数, 代码十分统一. 并且还不必去重.
def threeSumClosest(nums, target): if not nums or len(nums) < 3: return [] n = len(nums) # 排序 nums.sort() res = [] nearest_sum = sum(nums[:3]) if nums[0] >= target: return sum(nums[:3]) if nums[-1] <= target: return sum(nums[-3:]) for i in range(n-2): p1 = i + 1 p2 = n - 1 while p1 < p2: temp = nums[i] + nums[p1] + nus[p2] if abs(temp - target) < abs(nearest_sum - target): nearest_sum = temp if temp < target: p1 += 1 elif temp > target: p2 -= 1 else: return target return nearest_sum 工夫复杂度为$n^2$, 空间复杂度为$O(1)$
18. 四数之和
给定一个蕴含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不反复的四元组。
留神：
答案中不能够蕴含反复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组汇合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
这题的思路还是和下面几题的思路雷同
def fourSum(nums, target): if not nums or len(nums) < 4: return [] nums.sort() n = len(nums) res = [] for i in range(n-3): # 去重 if i > 0 and nums[i] == nums[i-1]: continue for j in range(i, n-2): p1 = j + 1 p2 = n - 1 # 去重 if j > i and nums[j] == nums[j-1]: continue while p1 < p2: temp = nums[i] + nums[j] + nums[p1] + nums[p2] if temp < target: p1 += 1 elif temp > target: p2 -= 1 else: res.append([nums[i], nums[j], nums[p1], nums[p2]]) # 去重 while p1 < p2 and nums[p1] == nums[p1+1]: p1 += 1 while p1 < p2 and nums[p2] == nums[p2-1]: p2 -= 1 p1 += 1 p2 -= 1 return res 工夫复杂度为$O(n^3)$, 空间复杂度为$O(1)$
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。
你不须要思考数组中超出新长度前面的元素。
这题要求原地批改数组, 那么显然, 咱们须要将反复的元素挪动到数组开端. 咱们能够应用双指针来解决这个问题.
- 设置两个指针p1, p2, 都初始化为0, 同时指向数组中第一个元素.
- 当p1地位的元素和p2地位的元素相等时, p2右移, 否则p1右移, 而后替换两个地位的值, p2右移.
- 反复执行第2步.
def removeDuplicates(nums): if not nums: return 0 if len(nums) < 2: return 1 # 同时指向第一个元素 p1 = p2 = 0 n = len(nums) while p2 < n: # 如果不相等, p1右移后， 替换两指针地位的值 if nums[p2] != nums[p1]: p1 += 1 nums[p2], nums[p1] = nums[p1], nums[p2] p2 += 1 return p1 + 1工夫复杂度为$O(n)$, 空间复杂度为$O(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。留神这五个元素可为任意程序。你不须要思考数组中超出新长度前面的元素。- 设置两个指针, p1, p2, 同时初始化为0
- 当p2元素不等于val时, 替换p1, p2地位元素. p1右移, p2右移
- 当p2元素等于val时, p2右移
- 回到第2步
def removeElement(nums, val): if not nums: return 0 if len(nums) == 1: return int(nums[0] != val) n = len(nums) p1 = p2 = 0 while p2 < n: if nums[p2] != val: nums[p1], nums[p2] = nums[p2], nums[p1] p1 += 1 p2 += 1 return p1还能够用首尾2个指针来挪动
- 设定两个指针p1,p2, 别离指向0和n-1.
- 如果p2地位元素等于val, 将其左移, 直至p2地位元素不等于val或者p2小于0.
- 当p1地位元素等于val时, 替换p1, p2地位的值, p1右移, p2左移.
- 当p2地位不等于val时, p1右移.
- 反复2-4步骤, 直至p1大于p2
def removeElement(nums, val): if not nums: return 0 if len(nums) == 1: return int(nums[0] != val) n = len(nums) p1 = 0 p2 = n - 1 # 这里须要有等号 while p1 <= p2: while p2 > p1 and nums[p2] == val: p2 -= 1 if nums[p1] == val: nums[p2], nums[p1] = nums[p1], nums[p2] p2 -= 1 p1 += 1 return p2 + 1工夫复杂度为$O(n)$, 空间复杂度为$O(1)$
75. 色彩分类
给定一个蕴含红色、红色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。
此题中，咱们应用整数 0、 1 和 2 别离示意红色、红色和蓝色。
留神:
不能应用代码库中的排序函数来解决这道题。
示例:
输出: [2,0,2,1,1,0]
输入: [0,0,1,1,2,2]
进阶：
- 一个直观的解决方案是应用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，而后依照0、1、2的排序，重写以后数组。
- 你能想出一个仅应用常数空间的一趟扫描算法吗？
这题首先想到的应该是计数排序, 工夫复杂度为$O(2n)$, 空间复杂度为$O(1)$.
但还有复杂度更低的办法, 同样还是双指针.
- 设置3个指针cur, p1, p2, 别离指向以后地位, 0的右边界和2的左边界, 初始化为0, 0, n-1.
- 当cur地位元素为0, 替换p1, cur地位的元素, p1, cur同时右移
- 当cur地位元素为2时, 替换p2, cur地位的元素, p2左移
- 当cur地位元素为1时, cur右移.
- 循环执行以上步骤, 直至cur 等于p2
def sortColors(nums): if not nums or len(nums) < 2: return cur = p1 = 0 p2 = len(nums) - 1 while cur < p2: if nums[cur] == 0: nums[cur], nums[p1] = nums[p1], nums[cur] p1 += 1 cur += 1 # Note: 当cur地位的值等于2时, cur不须要右移, 因为替换之后并不能保障cur地位的值不等于2. elif nums[cur] == 2: nums[cur], nums[p2] = nums[p2], nums[cur] p2 -= 1 else: cur += 1 工夫复杂度为$O(n)$, 空间复杂度为$O(1)$
88. 合并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
阐明:
- 初始化 nums1 和 nums2 的元素数量别离为 m 和 n 。
- 你能够假如 nums1 有足够的空间（空间大小大于或等于 m + n）来保留 nums2 中的元素。
示例:
输出:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3输入: [1,2,2,3,5,6]
最直观, 最简略的形式就是合并再排序, 对应的工夫复杂度为$O((m+n)log(m+n))$
但其实咱们能够应用双指针进一步升高复杂度
- 设置两个指针p1, p2, 别离指向nums1的m-1和nums2的n-1地位.
- 当p1地位元素大于p2地位元素时, 将nums1的m+n-1地位的值者只为p1地位的值, p1左移, 否则将nums1的m+n-1地位的值者只为p2地位的值, p2左移.
- 回到上一步, 直至p1<0或者p2<0
def merge(nums1, m, nums2, n): if not nums2: return nums1 i = m - 1 j = n - 1 while i >= 0 and j >= 0: if nums1[i] > nums[j]: nums1[i+j+1] = nums1[i] i -= 1 else: nums1[i+j+1] = nums2[j] j -= 1 if j >= 0: nums1[:j] = nums2[:j] return nums1工夫复杂度为$O(m)$或者$O(n)$, 空间复杂度为$O(1)$
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输出：1->2->4, 1->3->4
输入：1->1->2->3->4->4
def mergeTwoLists(l1, l2): p1 = l1 p2 = l2 # 初始化为一个长期节点 p0 = new_ln = ListNode(-1) while p1 and p2: if p1.val < p2.val: p0.next = p1 p1 = p1.next else: p0.next = p2 p2 = p2.next p0 = p0.next if p1: p0.next = p1 if p2: p0.next = p2 return new_ln.next工夫复杂度为$O(n)$, 空间复杂度为$O(1)$
剑指 Offer 21. 调整数组程序使奇数位于偶数后面
输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半局部。
示例：
输出：nums = [1,2,3,4]
输入：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
- 应用两个指针p1, p2, 别离初始化为0, n-1
- 当p1地位元素为奇数时, p1右移;
- 当p2地位元素为偶数时, p2左移
- 否则替换p1, p2地位元素.
def exchange(nums): if not nums or len(nums) < 2: return nums n = len(nums) p1 = 0 p2 = n - 1 while p1 < p2: if nums[p1] % 2: p1 += 1 elif not nums[p2] % 2: p2 -= 1 else: nums[p1], nums[p2] = nums[p2], nums[p1] return nums同样, 快慢指针也能够解决问题
def exchange(self, nums: List[int]) -> List[int]: if not nums or len(nums) < 2: return nums n = len(nums) p2 = p1 = 0 while p2 < n: if nums[p2] %2: nums[p1], nums[p2] = nums[p2], nums[p1] p1 += 1 p2 += 1 return nums工夫复杂度为$O(n)$, 空间复杂度为$O(1)$
总结
双指针的思路在数组和链表的题目中有着宽泛的利用, 这里次要介绍了数组中利用.
双指针分为两种, 快慢指针(这里将挪动频率不一样的称为快慢指针)和首尾指针. 首尾指针次要在数组中应用, 快慢指针在数组和链表中都有广泛应用.
快慢指针的基本思路是
- 同时初始化为0或者链表头节点
- 以后元素不满足条件时, 替换快慢指针指向的值; 慢指针右移, 快指针右移
- 否则, 快指针右移
- 反复2-3步骤
而首尾指针, 通常须要先将数组排序, 比方3数之和,4数之和等 而后依据具体情况抉择挪动首指针或者尾指针, 直至满足条件.
程度无限, 不免有谬误或有余的中央. 还请不吝赐教.