青岛网站推广系统,网站建设费 开办费,全国十大数字展馆设计公司,如何开发自己的软件作为 Leetcode 的第一题#xff0c;两数之和自然是知名度最高的#xff0c;从两数之和出发也有不少的衍生题目#xff0c;下面就让我们好好地解决它们。
1. 两数之和
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:record dict()for i…作为 Leetcode 的第一题两数之和自然是知名度最高的从两数之和出发也有不少的衍生题目下面就让我们好好地解决它们。
1. 两数之和
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:record dict()for i, num in enumerate(nums):if target - num in record:return [record[target - num], i]else:record[num] i最直接的思路是用哈希表把出现过的数字及其索引下标都用哈希表记录下来这样每当遍历新的数字就能快速找出 target - num 是否出现过若是则返回下标。
170. 两数之和 III - 数据结构设计
class TwoSum:def __init__(self):self.record dict()def add(self, number: int) - None:if number in self.record:self.record[number] 1else:self.record[number] 1def find(self, value: int) - bool:for num in self.record.keys():if value - num ! num:if value - num in self.record:return Trueelif self.record[num] 1:return Truereturn False这题是不断地向数组添加数字同时得能够检查数字是否为数组中某两个数字之和思路还是哈希表每当要对数字进行检查时这个数字就相当于 target遍历数组中的数字 num找到 target - num 是否也在数组中即可。要注意的是可能出现 target - num 等于 num 的情况而这种情况得 num 出现过两次才能返回 True所以要用字典统计 num 出现的次数。
167. 两数之和 II - 输入有序数组
class Solution:def twoSum(self, numbers: List[int], target: int) - List[int]:n len(numbers)left 0right n - 1while left right:total numbers[left] numbers[right]if total target:right - 1elif total target:left 1else:return [left1, right1]相较于上一题这题的条件是数组已经按非递减顺序排列这其实也给了我们一个新的思路因为有序数组总是与双指针联系在一起。所以说这题我们可以使用左右双指针 left 与 right当两数之和大于 target 时右指针左移当两数之和小于 target 时左指针右移正好等于 target 时返回答案注意下标从 1 开始。
15. 三数之和
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:ans []n len(nums)nums.sort()for i in range(n):# 除了首位置之外如果有多个重复的 nums[i]那就只考虑最后一个if i 0 and nums[i] nums[i - 1]:continueleft i 1right n - 1while left right:total nums[i] nums[left] nums[right]# total 太大右指针左移if total 0:right - 1# total 太小左指针右移elif total 0:left 1else:# total 符合条件ans.append([nums[i], nums[left], nums[right]])# 避免 left 1 与 left 一样while left right and nums[left] nums[left 1]: left 1# 避免 right - 1 与 right 一样while left right and nums[right] nums[right - 1]: right - 1# 确保了不会出现重复的答案left 1right - 1return ans从上一题得到的灵感就是可以将数组排序然后用双指针解法这对于三数、四数甚至更高的数之和都是适用的。在本题中我们首先遍历并固定第一个下标 i然后对它后面的区域进行双指针查找。由于不能出现重复的三元组所以去重点有两个 1、除了第一个位置以外凡是 nums[i] nums[i-1] 的就说明 i 这个位置的数与上一个位置的重复了直接考虑 i 1。如果用的是 nums[i] nums[i1] 判断就会把如 (-1, -1, 2) 这样的答案给忽略掉。 2、每当找到一个答案以后left 和 right 指针都要移动而它们应该跳过与当前位置数字相同的位置避免出现重复的三元组。
18. 四数之和
class Solution:def fourSum(self, nums: List[int], target: int) - List[List[int]]:ans []nums.sort()n len(nums)for i in range(n):if i 0 and nums[i] nums[i-1]:continuefor j in range(i1, n):if j i1 and nums[j] nums[j-1]:continueleft j 1right n - 1while left right:total nums[i] nums[j] nums[left] nums[right]if total target:right - 1elif total target:left 1else:ans.append([nums[i], nums[j], nums[left], nums[right]])while left right and nums[left] nums[left1]:left 1while left right and nums[right] nums[right-1]:right - 1left 1right - 1return ans与三数之和相比仅仅是多遍历了一个 j注意 j 的位置是从 i 1 开始的所以它的去重是 if j i1 and nums[j] nums[j-1]:
