Leetcode数组篇（中）| 8月更文挑战
前言
大家好，我也成为刷题大军的一员了，本次Leetcode数组篇一共分为三篇，此文是中篇，还有上篇和下篇。
每道题目我都会写明题目链接、题目描述以及是属于《剑指Offer》还是Leetcode题库，方便大家查阅观看。
另外，每道题目我都会尽可能地提供多种方案，每种方案的理解程度会从简单到困难，如果你刚好刷到这道题，希望能帮助到你!
最后，建议同种类型的题目一起刷，这样能大概摸索题目的常见套路，做起来效率也更高！
注：本文所有代码使用Golang语言实现
4.在排序数组中查找数字（Offer.53_1）
题目链接：leetcode-cn.com/problems/za…
题目描述：
统计一个数字在排序数组中出现的次数。
提示：
- nums 是一个非递减数组（关键）
解题思路： 方法一： 对于简单的数组题，首先考虑的还是遍历数组，并使用哈希表（Map）存储，数字作为key，出现的次数作为value，每出现一次，value+1，最后查询哈希表得到出现次数
- 时间复杂度：O（n）
- 空间复杂度：O（n）
// 方法一：暴力遍历
// time: 45.58% memory: 9.94%
func search1(nums []int, target int) int {
// 用哈希表存储出现的次数
numMap := map[int]int{}
for _, num := range nums {
if _, ok := numMap[num]; !ok {
numMap[num] = 1
} else {
numMap[num] += 1
}
}
// 在哈希表查询
count := 0
if _, ok := numMap[target]; ok {
count = numMap[target]
}
return count
}
方法二： 由于数组是递增的，所以相同的数肯定是相邻的，而且只要遍历的数大于目标值，则后面的数都无需比较，可以提前退出。
- 时间复杂度：O（n）
- 空间复杂度：O（1）
// 方法二：由于数组是递增的，所以相同的数肯定是相邻的，而且只要遍历的数大于目标值，即可退出
// time: 98.49% memory: 100%
func search2(nums []int, target int) int {
count := 0
for _, num := range nums {
if num == target {
count += 1
}
if num > target {
break
}
}
return count
}
注：推荐这种方法，代码行数少，理解简单，且Leetcode跑分高
方法三： 使用二分法，先通过二分法找到目标值，如果找到，分别向该目标值的左边和右边遍历（因为相同的值是相邻的），直到该目标值没有出现
- 时间复杂度：O（logN）+ 2O（N）≈ O（N）
- 空间复杂度：O（1）
// 方法三：使用二分法
// time: 6.45% memory: 58.31%
func search3(nums []int, target int) int {
count := 0
tar := binarySearch(nums, target)
if tar == -1 {
// 目标不存在
return count
}
// 遍历左半部分
for i := tar - 1; i >= 0; i-- {
if nums[i] == target {
count += 1
} else {
break
}
}
// 遍历右半部分
for i := tar; i < len(nums); i++ {
if nums[i] == target {
count += 1
} else {
break
}
}
return count
}
func binarySearch(nums []int, target int) (index int) {
left, right := 0, len(nums)-1
for left <= right {
m := (left + right) >> 1
if nums[m] < target {
left = m + 1
} else if nums[m] > target {
right = m - 1
} else {
return m
}
}
return -1
}
注：不推荐这种方法，代码行数较多，且Leetcode跑分低
5.[0～n-1]中缺失的数字（Offer.53_2）
题目链接：leetcode-cn.com/problems/qu…
题目描述：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
注：数组是递增的
解题思路： 方法一： 对于简单的数组题，首先考虑的还是遍历数组，规律就是用第二个数减第一个数，如果不为1说明是缺失数字，不过也有一些特殊情况，如下：
- 1.第一个数不为0，则缺失值为0
- 2.如果后一个数减前一个数不等于1，则缺失值为后一个数的索引（或者后一个数减一）
- 3.如果遍历后无缺失，则缺失值为：最后一个数+1
- 时间复杂度：O（N）
- 空间复杂度：O（1）
// 方法一：
// time: 91.08% memory: 61.82%
func missingNumber1(nums []int) int {
// 第一个数不为0，则缺失值为0
n := len(nums)
if n == 0 || nums[0] != 0 {
return 0
}
// 如果后一个数减前一个数不等于1，则缺失值为后一个数的索引（或者后一个数减一）
for i := 0; i < n-1; i++ {
if nums[i+1]-nums[i] != 1 {
// 等价 return nums[i+1] - 1
return i + 1
}
}
// 如果遍历后无缺失，则缺失值为：最后一个数+1
return nums[n-1] + 1
}
方法二： 由于数组是递增的，且根据题意这其实是一个等差数列，所以可以用预计总和减去实际数字的总和得到缺失的数字，预计总和可用等差数列的公式得到，实际数字的总和需要遍历得到
- 时间复杂度：O（N） 遍历时的复杂度
- 空间复杂度：O（1）
// 方法二：
// time: 91.22% memory: 99.66%
func missingNumber2(nums []int) int {
// 实际总和
count := 0
for _, num := range nums {
count += num
}
// 理想总和
n := len(nums) + 1
// 等差数列求和
S := n*0 + (n*(n-1))/2
return S - count
}
方法三： 使用二分法，二分法利用这道题目的一个隐含规律，即索引的值和存储的值是相等的，如果不等，则说明发生了错位。
二分的时候，如果值相等，说明左半区间无缺失，所以接下来要去右半区间搜索；如果值不等，则右半区间无缺失，需要去左半区间搜索。
- 时间复杂度：O(logN)
- 空间复杂度：O(1)
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) >> 1
if nums[mid] != mid {
// 去左半区间搜索
right = mid
} else {
// 去右半区间搜索
left = mid + 1
}
}
// 0~n-1都没有发现缺失值，则缺失值为最后一个数+1
if left == len(nums)-1 && nums[left] == left {
return left + 1
}
return left
注：感觉Leetcode的跑分不是很准确，O(logN)跑出来的效果不一定就比O(N)好
6.两数之和（Leet.1）
题目链接：leetcode-cn.com/problems/tw…
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
解题思路： 方法一： 对于简单的数组题，首先考虑的还是暴力遍历，选取第一个元素，接着从第二个元素开始遍历，直到找到和为目标值的两个整数（本质上是遍历二维数组）
- 时间复杂度：O（n2）
- 空间复杂度：O（1）
// 方法一：暴力遍历
// time: 18.93% memory: 68.73%
func twoSum1(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
方法二： 使用哈希表。我们可以将查找的两个数定为A和B，目标值定为C，可以得到A+B=C，即B=C-A，A为遍历的值，B为需要匹配的值，C为目标值。
此时遍历数组，我们使用哈希表的key存储B的值，value存储B的索引，如果需要查找的值在哈希表存在，返回；如果不存在，把当前值及其索引存入哈希表。
- 时间复杂度：O（n）
- 空间复杂度：O（n）
// 方法二：使用哈希表
// time: 96.99% memory: 52.41%
func twoSum2(nums []int, target int) []int {
// key是值，value是下标
diffMap := map[int]int{}
for i := 0; i < len(nums); i++ {
a := nums[i]
b := target - a
if _, ok := diffMap[b]; ok {
// 注意返回的是下标
return []int{i, diffMap[b]}
}
diffMap[a] = i
}
return []int{}
}
写在最后
本篇内容就先讲这三道题，如果错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！