最近刷题遇到了好几次这个类型的题,于是在此做个总结。
两数之和
利用 Map 来进行记录和快速查找
题目大意:给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
思路:我们只讨论最优解,一次遍历就能够找到这两个数。我们利用 Map 来存放已经遍历过的数字和其对应的下标。对于当前遍历到的第 i
个数字,如果我们能够在 Map 的中找到 key 为 target-nums[i]
的数据,说明找到了那两个整数,返回它们的下标即可。
时间复杂度:$O(N)$,其中 $N$ 是数组中元素的个数。对于每一个元素 x
,我们可以 $O(1)$ 地寻找 target-x
。
代码:
1 | class Solution { |
三数之和
先对数组进行排序,固定其中一个指针指向数字
base
,再用双指针在base
之后的区域内寻找合适的位置
题目大意:给你一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0
且不重复的三元组。
思路:
- 对数组进行排序
- 遍历排序后的数组:
- 若
nums[i] > 0
:因为是排序后的数组,所以不可能有三个数之和等于0,直接返回结果; - 若
nums[i] == nums[i - 1]
:跳过,避免出现重复解; - 令左指针
l = i + 1
,右指针r = nums.length - 1
,当l < r
时执行循环:- 当
nums[i] + nums[l] + nums[r] == 0
,执行循环,跳过左边界和右边界上重复的元素,避免重复解,同时将l
和r
移动到下一位置,寻找新的解; - 若
nums[i] + nums[l] + nums[r] > 0
,说明nums[r]
太大,右边界r
左移; - 若
nums[i] + nums[l] + nums[r]< 0
,说明nums[l]
太小,左边界l
右移;
- 当
- 若
时间复杂度:$O(N^{2})$,其中 $N$ 是数组的长度。数组排序 $O(NlogN)$,遍历数组 $O(N)$,双指针遍历 $O(N)$,总体时间复杂度为 $O(NlogN) + O(N)*O(N)$。
代码:
1 | class Solution { |
四数之和
和三数之和类似,只不过是固定了前两个指针,然后利用双指针移动来寻找满足条件的解。
题目大意:给定一个包含 n
个整数的数组 nums
和一个目标值 target
,判断 nums
中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target
相等?找出所有满足条件且不重复的四元组。
思路:
- 对数组进行排序
- 两层 for 遍历排序后的数组:
- 若
nums[i] + nums[j] + nums[nums.length - 2] + nums[nums.length - 1] < target
,当前组合所能产生的最大值小于target
,跳过; - 若
nums[i] == nums[i - 1]
或者nums[j] == nums[j - 1]
,跳过,避免出现重复解; - 令左指针
l = j + 1
,右指针r = nums.length - 1
,当l < r
时执行循环:- 若
nums[i] + nums[j] + nums[l] + nums[r] == target
,执行循环,跳过左边界和右边界上重复的元素,避免重复解,同时将l
和r
移动到下一位置,寻找新的解; - 若
nums[i] + nums[j] + nums[l] + nums[r] > target
,说明nums[r]
太大,右边界r
左移; - 若
nums[i] + nums[j] + nums[l] + nums[r] < target
,说明nums[l]
太小,左边界l
右移;
- 若
- 若
时间复杂度:$O(N^{3})$,其中 $N$ 是数组的长度。排序的时间复杂度是 $O(NlogN)$,枚举四元组的时间复杂度是 $O(N^{3})$,因此总时间复杂度是 $O(NlogN + N^{3})$
代码:
1 | class Solution { |