Leetcode数组篇（下）
前言
大家好，我也成为刷题大军的一员了，本次Leetcode数组篇一共分为三篇，此文是下篇，还有上篇和中篇。
每道题目我都会写明题目链接、题目描述以及是属于《剑指Offer》还是Leetcode题库，方便大家查阅观看。
另外，每道题目我都会尽可能地提供多种方案，每种方案的理解程度会从简单到困难，如果你刚好刷到这道题，希望能帮助到你!
最后，建议同种类型的题目一起刷，这样能大概摸索题目的常见套路，做起来效率也更高！
注：本文所有代码使用Golang语言实现
7.寻找两个正序数组的中位数（Leet.4）
题目链接：leetcode-cn.com/problems/me…
题目描述：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
中位数，即中间的那个数，即在这组数据中，有一半的数据比他大，有一半的数据比他小
解题思路：
方法一： 方法一是比较简单的思路，即合并两个数组，并重新进行排序（也可以在合并的过程中就进行排序），即可得到中位数
- 时间复杂度：O（n + m）
- 空间复杂度：O（n + m）
// 方法一：先合并，再求中位数
// time: 44.09% memory: 6.85%
func findMedianSortedArrays1(nums1 []int, nums2 []int) float64 {
// 先合并数组，且在合并过程中顺便排序
merge := []int{}
n1, n2 := len(nums1), len(nums2)
point1, point2 := 0, 0
for n1 > point1 && n2 > point2 {
if nums1[point1] < nums2[point2] {
merge = append(merge, nums1[point1])
point1 += 1
} else {
merge = append(merge, nums2[point2])
point2 += 1
}
}
// 如果是nums1先合并完，则将nums2剩余合并（因为nums1和nums2都是正序）
if n1 <= point1 {
merge = append(merge, nums2[point2: n2]...)
}else{
// nums2先合并完，则将nums1剩余合并
merge = append(merge, nums1[point1: n1]...)
}
return calMedium(merge)
}
// 计算中位数
func calMedium(nums []int) float64 {
count := len(nums)
if count%2 == 1 {
return float64(nums[count/2])
} else {
return (float64(nums[count/2]) + float64(nums[count/2-1])) / 2
}
}
方法二： 方法二是对方法一的优化，其实我们并不需要合并数组后才知道中位数，当我们知道两个数组的长度时，其实就已经知道中位数的位置了，这种方法的优点在于可以节省内存。
- 时间复杂度：O（n + m）
- 空间复杂度：O（1）
// 方法二：使用指针代替数组存储，节省内存
// time: 43.52% memory: 77.48%
func findMedianSortedArrays2(nums1 []int, nums2 []int) float64 {
n := len(nums1)
m := len(nums2)
total := n + m
// point1，point2分别代表两个数组的指针，会不断移动
point1, point2 := 0, 0
// prev，next分别代表上一个值，和下一个值，因为如果数组长度总和为偶数，需要用到中间两个数之和
prev, next := -1, -1
// 不管两个数组总和是单数，还是偶数，都需要遍历 total/2+1 次
for i := 0; i <= total/2; i++ {
prev = next
if point1 < n && (point2 >= m || nums1[point1] < nums2[point2]) {
next = nums1[point1]
point1 += 1
} else {
next = nums2[point2]
point2 += 1
}
}
// 双数
if total%2 == 0 {
return float64(prev+next) / 2
} else {
return float64(next)
}
}
上述代码有几个点需要解释说明下：
- 1.为什么是遍历
total/2 + 1次？假设用 total 表示合并后数组的长度，如果是奇数，我们需要知道第 （total+1）/2 个数就可以了；如果是偶数，我们需要知道第 total/2 和 total/2+1 个数，也是需要遍历 total/2+1 次。所以不管是奇数还是偶数，我们都是遍历total/2+1次。 - 2.为什么需要 prev 指针？其实上面的代码注释也说到了，由于合并后的数组长度如果为偶数，我们需要用到中间两个数来计算中位数，所以这里需要增加一个 prev 指针存储上一个值
- 3.关于
point1 < n && (point2 >= m || nums1[point1] < nums2[point2])的理解，其实在遍历的时候，我们需要考虑到 nums1 或者 nums2 的长度都不一定比 total/2 + 1 长，所以不这么判断的话，就会有数组越界的可能。
方法三： 上述两个算法的时间复杂度都是O（n + m），但都达不到这道题目的进阶要求：O(log (m+n))，而当遇到排好序的数组，且时间复杂度要求为log，我们很容易就想到二分法。
所以我们不妨换一种思路，求中位数其实相当于第 k 小的数字的一种情况，相当于要在合并后的数组中求第 k 小的数字。详情可以参考这里的解法
- 时间复杂度：O(log (m+n))
- 空间复杂度：O（1）
// 方法三：二分查找，有序一般需要考虑二分
// 方法二其实是通过遍历的方法一个一个丢弃非中位数的值，而方法三是通过二分的方法丢弃非中位数的值
// time: 98.72% memory: 78.26%
func findMedianSortedArrays3(nums1 []int, nums2 []int) float64 {
n := len(nums1)
m := len(nums2)
// 将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k
// 当 n+m 为偶数，比如14，left=7，right=8，即我们要得到第7小和第8小的值，相加除以2正好为中位数
// 当 n+m 为奇数，比如15，left=8，right=8，即我们要求两次第8小的值，相加除以2也是中位数
left := (n + m + 1) / 2
right := (n + m + 2) / 2
return float64(getKth(nums1, 0, n-1, nums2, 0, m-1, left)+getKth(nums1, 0, n-1, nums2, 0, m-1, right)) / 2
}
// ！！！获取第K小的数字！！！
func getKth(nums1 []int, start1, end1 int, nums2 []int, start2, end2 int, k int) int {
// len1、len2 每经过一轮迭代后，两个数组的当前长度，因为每一轮迭代都会排除非中位数的值
len1 := end1 - start1 + 1
len2 := end2 - start2 + 1
// 让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
if len1 > len2 {
return getKth(nums2, start2, end2, nums1, start1, end1, k)
}
// 当nums1为空，没有继续寻找的必要，此时第k小的数字只需在nums2查找
// start2 是当前索引，k-1是因为索引从0开始
if len1 == 0 {
return nums2[start2+k-1]
}
// 每一轮迭代k都会除以2，所以k最终会等于1（或者某个数组为空）
// 当 k=1，即求第1小的数字，那只要拿nums1和nums2第一个数进行比较即可（nums1和nums2的长度会不断减少）
if k == 1 {
return min(nums1[start1], nums2[start2])
}
// k/2 有可能大于数组长度，所以要取最小值
i := start1 + min(len1, k/2) - 1
j := start2 + min(len2, k/2) - 1
if nums1[i] > nums2[j] {
// 如果数组1的值大于数组2，则说明数组2的前j个数都不符合要求，所以 start 变为 j+1
// j-start2+1 表示排除的长度，所以 k-(j-start2+1) 得到最新的k
return getKth(nums1, start1, end1, nums2, j+1, end2, k-(j-start2+1))
} else {
return getKth(nums1, i+1, end1, nums2, start2, end2, k-(i-start1+1))
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
注：上面的代码是根据Leetcode的解法用Go重写的，并加上自己的理解
8.盛水最多的容器（Leet.11）
题目链接：leetcode-cn.com/problems/co…
题目描述：
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
解题思路： 方法一： 一开始的思路是怎么样才能找到两根距离最长，高度又较高的柱子，但是转念一想，这个思路其实不太对，对机器来说也很难实现。
所以这道题其实可以转换为寻找两个数，且这两个数求得的容量最大，所以最简单的办法就是暴力遍历，即遍历二维数组，并用一个变量存储最大容量。
- 时间复杂度：O（n2）
- 空间复杂度：O（1）
// 方法一：暴力遍历
// time/memory: 超出时间限制
func maxArea1(height []int) int {
max := 0
for i := 0; i < len(height)-1; i++ {
for k := i + 1; k < len(height); k++ {
area := (k - i) * getMin(height[i], height[k])
if area >= max {
max = area
}
}
}
return max
}
func getMin(a, b int) int {
if a > b {
return b
}
return a
}
注：上述代码在Leetcode无法跑通，原因是超出时间限制，所以仅供参考！！！
方法二： 使用双指针。双指针即定义左右两个指针，以及使用一个变量存储最大容量，以上述题目数组为例，第一轮计算后，容量为 min(1, 7) * 8 = 8。当进行第二轮计算时，我们需要移动一根柱子，由于容量大小由高度低的柱子决定，所以我们需要移动左边的柱子（指针），并再计算容量，以此类推，当左右两个指针重合（相等）时，停止计算。
- 时间复杂度：O（n）
- 空间复杂度：O（1）
// 方法二：双指针
// time: 89.15% memory:30.09%
func maxArea2(height []int) int {
left := 0
right := len(height) - 1
area := 0
for left < right {
tmp := getMin(height[left], height[right]) * (right - left)
area = getMax(tmp, area)
if height[left] > height[right] {
right -= 1
} else {
left += 1
}
}
return area
}
func getMin(a, b int) int {
if a > b {
return b
}
return a
}
func getMax(a, b int) int {
if a > b {
return a
}
return b
}
注：双指针的解法非常简单，但这道题难就难在为什么用双指针的解法是对的，不会漏掉某些情况吗？
我个人是这样理解的（以例题的数组为例）： 第一轮计算，假设左指针高度为x，容器的宽度为t，此时不管右指针怎么移动，容量都不会超过 x * t。 第二轮计算，我们需要移动一根柱子，由于左指针小于右指针，所以肯定是移动左指针，而在第二轮的计算中我们也不会再用到第一根柱子，第一根柱子可以视为废弃。
所以每一轮其实我们都可以废弃掉一根柱子，从而不断减少我们的数组规模，并再用同样的思路进行下一轮的计算。
9.三数之和（Leet.15）
题目链接：leetcode-cn.com/problems/3s…
题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思路： 方法一： 排序+双指针。该方法具体步骤如下：
- 1.判断数组的长度是否小于3，因为小于3无法满足条件，直接返回
- 2.对数组进行排序，方便后续判断，也方便去除重复解
- 3.遍历数组，并对数组的剩余部分用双指针求解出满足条件的三元组
如何去除重复？ 要想去除重复的三元组，其实只要满足相邻的两个数不相等即可。以数组 [0, 1, 2, 2, 2, 3]为例，使用三重循环遍历，一开始可以得到（0,1,2）三元组，但由于后面2重复，这时候会产生重复，所以我们需要跳到下一个不等的数，即3，得到（0,1,3）三元组。
详细解法可以参考这里
- 时间复杂度：O（n2）。数组排序 O(NlogN)，遍历数组O(N)，双指针遍历O(N)，整体复杂度为 O(NlogN) + O(N) * O(N) = O（n2）
- 空间复杂度：O（1）
// 方法一：排序+双指针
// time：97.10% memory：71.82%
func threeSum1(nums []int) [][]int {
res := [][]int{}
n := len(nums)
// 当数组长度小于3时，无法满足条件，直接返回
if n < 3 {
return res
}
// 对数组进行排序，既方便判断，也方便查找
sort.Ints(nums)
for i := 0; i < n; i++ {
// 当数组的第一个值大于0，后面的值都会大于0，相加不可能等于0，所以没有查找的必要
if nums[i] > 0 {
return res
}
// 去除重复解，相邻两个数如果相等，会存在重复解
// n > 0 是为了避免数组越界
if i > 0 && nums[i] == nums[i-1] {
continue
}
// 通过双指针找到满足 a+b+c=0 的三元组（不一定只有一个）
left := i + 1
right := n - 1
for left < right {
if nums[i]+nums[left]+nums[right] == 0 {
res = append(res, []int{nums[i], nums[left], nums[right]})
// 相邻的值相等，即有重复解，跳到下一个不等的数
// 重复的值有可能不止一个，如[0, 1, 2, 2, 2, 3]，所以需要用到一个while循环
for left < right && nums[left] == nums[left+1] {
left += 1
}
// 同理，去除重复解
for left < right && nums[right] == nums[right-1] {
right -= 1
}
left += 1
right -= 1
} else if nums[i]+nums[left]+nums[right] > 0 {
// 若和大于0，说明 nums[right] 太大，需要往左移动
right -= 1
} else {
left += 1
}
}
}
return res
}
数组篇总结
到了这里，本次数组篇就暂告一段落了。在开篇的时候，我就提到过建议同种类型的题目一起刷，这样能摸索这类题目的常见套路，在刷了这九道题后，我也有一些心得分享给大家，希望对大家有帮助！
我个人将数组的常见解法分为这几种：遍历法、排序法、空间换时间法、二分法以及双指针法。
遍历法： 其实就是遍历数组，这种方式简单粗暴，能够解决大部分问题，缺点就是时间复杂度较高，有时并不一定能满足题目要求，比如上述第8题（盛水最多的容器），用暴力遍历就会超时。
排序法： 我觉得遇到数组题，需要有排序的意识，有时候通过排序后，整道题会变得简单很多，比如上述的第九题。而且排序法往往会和遍历、二分法等搭配，是一种辅助手段。
二分法：遇到数组查找，特别是排好序的数组，二分法几乎是少不了的，二分法的原理比较简单，而且还能达到logN的复杂度。不过二分法也有复杂的情况，比如上述的第七题，求中位数。
双指针法：双指针是这阵子刷题以来学到的一种方法，通过利用头尾指针（左右指针），以及题目中隐藏的规律（正序、等于0等），可以将O（n2）的复杂度降低到O（n），是一种跟二分法同样重要的方法，典型题目如上述的第八题和第九题。
写在最后
本文如有错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！