数组

理论基础

数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力。也就是说，想法很简单，但实现起来可能就不是那么回事了

首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题，数组是存放在连续内存空间上的相同类型数据的集合

数组可以方便的通过下标索引的方式获取到下标所对应的数据，需要两点注意的是

数组下标都是从0开始的。
数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以在删除或者增添元素的时候，就难免要移动其他元素的地址

二分查找

704. 二分查找 - 力扣（LeetCode）

给定一个升序的整数数组和一个目标值，返回数组中目标值的下标，若没有返回-1

思路一：遍历数组

1
2
3
4
5
6
7
8


func search(nums []int, target int) int {
    for i, v := range nums {
        if v == target {
            return i
        }
    }
    return -1
}

时间复杂度：O(n)
空间复杂度：O(1)

思路二：二分查找，定义初始区间索引为给定数组索引；比较区间的中间值和目标值的大小，若区间中间值小于目标值，说明目标值在区间中间值右半部分，调整区间左索引为中间索引+1；若区间中间值大于目标值，说明目标值在区间中间值左半部分，调整区间右索引为中间索引-1；若区间中间值等于目标值，返回中间值索引

注意：

调整区间索引时要设为中间索引的前一个或后一个
使用二分查找的数组要是有序的
求中间索引时为了防止求和后整数溢出，可以用left+(right-left)/2，即先求出区间元素个数的一半，再从左边界前进该个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right { // 当left = right时[left, right]依然有效
        mid := left + (right - left) / 2 // 获得区间中间索引
        if nums[midIdx] == target {
            return midIdx // 找到目标值 
        } else if nums[midIdx] < target {
            left = midIdx + 1 // 目标值在右区间
        } else { // nums[midIdx] > target
            right = midIdx - 1 // 目标值在左区间
        }
    }
    return -1
}

时间复杂度：O(logn)
空间复杂度：O(1)

搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引，如果目标值不存在于数组中，返回它将会被按顺序插入的位置，必须使用时间复杂度为 O(log n) 的算法

只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的

二分查找若直到左区间大于右区间仍未找到目标值，则看最后左区间等于右区间时的元素值，若最后的中间值大于目标值，则返回该中间值下标，否则返回该中间值下一元素下标

简化：若二分查找结束没找到目标值，直接返回区间右边界加一或左边界；因为若最后的中间值小于目标值，说明目标值在右半区间，目标值要插入到最后中间值的后面一个，而此时只调整了左边界，右边界没动，还指向最后的中间值；若最后的中间值大于目标值，说明目标值在左半区间，目标值要插入到最后的中间值位置，此时右边界被移到最后中间值的前一个元素，右边界再加一刚好是最后的中间值位置；若最后的中间值等于目标值，则插入到最后的中间值位置或后面一个都可以

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return mid   
        } else if nums[mid] < target {
            left = mid + 1 // 目标值在右半区间
        } else {
            right = mid - 1 // 目标值在左半区间
        }
    }
    return right + 1 // 返回插入位置
    // return left
}

时间复杂度：O(log n)
空间复杂度：O(1)

暴力解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func searchInsert(nums []int, target int) int {
    // 遍历数组
    for i, v := range nums {
        // 判断元素是否大于或等于目标值
        if v >= target {
            // 直接返回当前索引
            return i
        }
    }
    // 目标值最大
    return len(nums)
}

时间复杂度：O(n)
空间复杂度：O(1)

在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

给定一个递增数组和目标值，找出给定目标值在数组中的开始位置和结束位置，如果数组中不存在目标值，返回 [-1, -1]，必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

思路一：数组中含有重复元素，用二分查找到目标元素后，再向两边继续查找相同元素并记录下标，直到遇到不同元素，返回目标值的区间

注意：

找到目标区间后直接跳出循环返回结果
结果区间要初始化为0，避免当给定数组中只有一个元素且刚好是目标值时，向两边找不到不同元素，最后直接返回结果区间的初始值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


func searchRange(nums []int, target int) []int {
    left, right := 0, len(nums)-1
    resLeft, resRight := 0, 0
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            for i := mid; i < len(nums); i++ { // 从目标值向右遍历
                if nums[i] != target {
                    break
                }
                resRight = i // 更新右边界
            }
            for i := mid; i >= 0; i-- { // 从目标值向左遍历
                if nums[i] != target {
                    break
                }
                resLeft = i // 更新左边界
            }
            return []int{resLeft, resRight}
        } else if nums[mid] > target {
            right = mid - 1 // 目标值在左区间
        } else {
            left = mid + 1 // 目标值在右区间
        }
    }
    return []int{-1, -1}
}

时间复杂度：最坏情况会退化为O(n)

思路二：分别用两个二分查找左右边界；在找左边界的二分查找中找到目标值后需要判断目标值的上一个元素是否与目标值不同，若不同或已经是数组的第一个元素则说明此中间值是左边界，否则继续更新右边界向左半区间查找；同理，在找右边界的二分查找中找到目标值后需要判断目标值的下一个元素是否与目标值不同，若不同或已经是数组最后一个元素则说明此中间值是右边界，否则继续更新左边界向右半区间查找

注意：在遇到目标值后，若判断不是边界，则需要更新二分查找边界

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func searchRange(nums []int, target int) []int {
    left := searchLeft(nums, target)
    right := searchRight(nums, target)
    return []int{left, right}
}
func searchLeft(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target { // 找到目标值
            if mid == 0 || nums[mid-1] != target {
                return mid
            } else { // 不是第一个目标值
                right = mid - 1 // 向左搜索更新右边界
            }
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // 没找到左边界
}
func searchRight(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target { // 找到目标值
            if mid == len(nums)-1 || nums[mid+1] != target {
                return mid
            } else { // 不是最后一个目标值
                left = mid + 1 // 向右搜索更新左边界
            }
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1 // 没找到右边界
}

时间复杂度：O(log n)
空间复杂度：O(1)

x 的平方根

69. x 的平方根 - 力扣（LeetCode）

给你一个非负整数，返回算术平方根，结果只保留整数部分，舍去小数部分

一个数x的算术平方根一定在0~x/2，升序数组，考虑使用二分查找法找到目标元素

在二分查找过程中有三种情况

如果这个整数的平方等于输入整数，那么我们就找到了这个整数；
如果这个整数的平方大于输入整数，那么这个整数肯定不是我们要找的那个数；
如果这个整数的平方小于输入整数，那么这个整数可能是我们要找的那个数 (算术平方根为小数时只保留整数)。

若算术平方根是小数，则最后一轮循环中，mid是第一个大于x/mid的值，所以在左区间寻找，执行right = mid -1 ，此时right < left，结束循环，right就是只保留整数的算术平方根

注意：

若使用mid == x/mid判断，则2/0会报错，进入循环前判断是否给定整数为0和1，此外，左边界应初始化为0，不能初始化为0；若左区间初始化为0，给定整数为2，由于右边界初始化为x/2，mid会算出0，x/0报错；左右边界可初始化为[0,x]或[1,x/2]，[0,x]相比[1,x/2]刚开始会多判断一次
若直接使用mid*mid == x判断，乘数可能会发生整数溢出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func mySqrt(x int) int {
    left, right := 0, x
    if x <= 1 {
        return x
    }
    for left <= right {
        mid := left + (right-left)/2
        if mid == x/mid {
            return mid
        } else if mid < x/mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return right
}

时间复杂度：O(log n)
空间复杂度：O(1)

有效的完全平方数

367. 有效的完全平方数 - 力扣（LeetCode）

给给定一个正整数。若是一个完全平方数，则返回 true ，否则返回 false ，例如16是完全平方数，因为4*4=16，14不是完全平方数，因为3.742 * 3.742 = 14，但 3.742 不是一个整数

用二分法查找给定整数的平方根，若能找到返回true，否则返回false

注意：

判断条件不能写mid == num/mid，只能写mid * mid == num，因为num/mid为int类型，会导致结果错误

例如：当num=5, mid=2时，mid == num/mid为true，而num并不是完全平方数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func isPerfectSquare(num int) bool {
    left, right := 1, num/2
    if num <= 1 {
        return true
    }
    for left <= right {
        mid := left + (right-left)/2
        if mid*mid == num {
            return true
        } else if mid*mid < num {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

时间复杂度：O(log n)
空间复杂度：O(1)

移除元素

27. 移除元素 - 力扣（LeetCode）

给定一个数组和目标值，原地移除数组中等于目标值的元素，返回移除后数组的长度，要求不能使用额外的数组空间

思路一：暴力，外层循环遍历数组，每遇到一个目标值就在内层循环中将后面的所有元素前移一个单位；前移结束后设置下一次遍历位置为仍为当前下标，数组长度减一；若当前元素不是目标值，则下一次遍历位置为下一元素

注意：遍历结束的标志是移除后数组的长度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func removeElement(nums []int, val int) int {
    size := len(nums)
    for i := 0; i < size; i++ {
        if nums[i] == val {
            for j := i; j < len(nums)-1; j++ {
                nums[j] = nums[j+1] // 元素前移一个单位
            }
            i--    // 下次循环仍从当前元素位置开始
            size-- // 数组长度减一
        }
    }
    return size
}

时间复杂度：O(n²)
空间复杂度：O(1)

思路二：双指针（快慢指针），在一个循环中完成两个循环的工作；快指针寻找与目标值不同的新元素，慢指针指向要更新的下标；将快指针指向的新元素更新到前面慢指针指向的元素；当快指针遍历结束后，返回最后慢指针指向的下标即可

快慢指针都从头出发；快指针遍历数组，当快指针指向的元素与目标值不同时，将快指针指向的元素值赋给慢指针指向的元素，然后慢指针前进一步（快指针遇到与目标值不同的元素时，快慢指针同步前进）；当快指针指向的元素与目标值相同时，慢指针不动此时指向要更新的元素，快指针继续前进，快指针遇到的元素若仍与目标值相同，慢指针仍不动，快指针继续前进，直到快指针遇到与目标值不同的元素，此时快指针的指向的元素会赋给此时慢指针指向的要更新的元素，更新后慢指针前进一个单位指向下一个要更新元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func removeElement(nums []int, val int) int {
    slowIdx := 0
    for fastIdx := 0; fastIdx < len(nums); fastIdx++ {
        if nums[fastIdx] != val {
            nums[slowIdx] = nums[fastIdx] // 更新元素
            slowIdx++                     // 慢指针前进一步
        }
    }
    return slowIdx
}

时间复杂度：O(n)
空间复杂度：O(1)

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

给定一个递增数组，原地移除数组中重复的元素，使每个元素只出现一次，返回移除后数组的长度，要求不能使用额外的数组空间

双指针法：快指针遍历数组寻找新元素，慢指针指向要更新的元素下标，将快指针指向的元素更新到慢指针指向的元素，快指针遍历结束后，返回慢指针指向的下标

初始时将第一个元素置为目标值，快慢指针遍历从第二个元素开始，当快指针遇到新元素，更新目标值为新元素，更新慢指针指向元素的值，慢指针前进

简化：省去目标值变量，判断快指针是否遇到新元素，直接与快指针指向的前一个元素比较

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func removeDuplicates(nums []int) int {
    slowIdx := 1
    for fastIdx := 1; fastIdx < len(nums); fastIdx++ {
        if nums[fastIdx] != nums[fastIdx-1] { // 找到新元素
            nums[slowIdx] = nums[fastIdx]     // 更新慢指针指向元素
            slowIdx++                         // 慢指针前进
        }
    }
    return slowIdx
}

时间复杂度：O(n)
空间复杂度：O(1)

移动零

283. 移动零 - 力扣（LeetCode）

给定一个数组，将数组中所有的0都移到末尾，要求其余元素顺序不变，必须在不复制数组的情况下原地对数组进行操作

暴力：遍历数组，每遇到一个0就将所有元素前移一个，同时将末尾元素置为0，时间复杂度O(n²)

双指针法：类似用快慢指针移除元素的操作，目标值为0，快指针遍历数组，慢指针标记要更新的元素，当快指针遇到非目标值说明要更新慢指针指向的目标值

由于是将0移到数组末尾，并非是完全移除，所有当快指针找到不为0的数时，将慢指针和快指针的值交换即可，这样会将非0值逐个换到前面的0所在位置

1
2
3
4
5
6
7
8
9


func moveZeroes(nums []int) {
    slowIndex := 0
    for fastIndex := 0; fastIndex < len(nums); fastIndex++ {
        if nums[fastIndex] != 0 {
            nums[slowIndex], nums[fastIndex] = nums[fastIndex], nums[slowIndex] // 更新慢指针指向元素
            slowIndex++                                                         // 慢指针前进
        }
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

比较含退格的字符串

844. 比较含退格的字符串 - 力扣（LeetCode）

给定两个字符串，# 代表退格字符，若两者相等返回 true ，否则返回false，如果对空文本输入退格字符，文本仍为空

思路一：快慢指针

对两个字符串分别使用快慢指针，得到退格后的有效字符串，最后直接用==判断：快指针遍历字符串，当快指针遇到有效字符时，则将快指针指向值赋给慢指针指向值（表示退格符后有效元素前移替换了删除的元素），最后慢指针前进一个单位；当快指针遇到退格符且慢指针指向非首时，则慢指针回退一个（指向要删除的元素）；

注意：由于字符串不可修改，所以需要将字符串不可变性

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func backspaceCompare(s string, t string) bool {
    // 判断俩有效字符串是否相等
    return getString(s) == getString(t)
}
func getString(s string) string {
    slow := 0
    // 将字符串转换为字符数组
    byteArray := []byte(s)
    // 快指针遍历字符数组
    for fast := range byteArray {
        // 判断是否遇到有效字符
        if byteArray[fast] != '#' {
            // 更新慢指针值(替换元素)
            byteArray[slow] = byteArray[fast]
            // 慢指针后移
            slow++
        } else if slow != 0 {
            // 慢指针前移(指向删除元素)
            slow--
        }
    }
    // 返回有效字符串
    return string(byteArray[:slow])
}

时间复杂度：O(n+m)
空间复杂度：O(n+m)

思路二：栈

匹配（消除）问题也是栈的擅长所在：两个字符串分别用两个栈，遇到退格符，栈顶弹出，遇到有效字符，入栈，最后比较两个栈里元素是否相等

注意：

for range遍历字符串时，每个字符是rune类型
每次遇到弹栈，都要先判栈非空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func backspaceCompare(s string, t string) bool {
    return getSting(s) == getSting(t)
}
func getSting(s string) string {
    stack := make([]rune, 0)
    // 遍历字符串s
    for _, ch := range s {
        // 判断是否为有效字符
        if ch != '#' {
            // 入栈
            stack = append(stack, ch)
        } else if len(stack) != 0 {
            // 弹栈
            stack = stack[:len(stack)-1]
        }
    }
    return string(stack)
}

时间复杂度:O(n + m)
空间复杂度:O(n + m)

思路三：模拟退格

由于 # 号只会消除左边的一个字符，所以对右边的字符无影响，所以选择从后往前遍历 S，T 字符串。

思路解析：

准备两个指针分别指向俩字符串的末位字符，再准备两个变量 skipS，skipT存俩字符串中的 # 数量
从后往前遍历 S，所遇情况有三，如下所示：
1. 若当前字符是 #，则 skipS 自增 1；
2. 若当前字符不是 #，且 skipS 不为 0，则 skipS 自减 1；
3. 若当前字符不是 #，且 skipS 为 0，则代表当前字符不会被消除，我们可以用来和 T 中的当前字符作比较。

若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false，若 S，T 都遍历结束，且都能一一匹配，则返回 true。

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

若该字符为退格符，则我们需要删除一个普通字符，我们让 skip 加 1；
若该字符为普通字符：
- 若 skip 为 0，则说明当前字符不需要删去；
- 若 skip 不为 0，则说明当前字符需要删去，我们让 skip 减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止

注意：

实现逻辑上比较复杂，很难完整考虑所有情况

具体代码可以去看力扣官方题解

时间复杂度：O(n+m)
空间复杂度：O(1)

有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）

给定一个非递减的整数数组，要求返回每个数字的平方组成的新数组，新数组也要非递减

考虑到原数组中有负数，原数组元素逐个直接平方后可能会出现递减数组

思路一：暴力，逐个元素平方，然后对元素排序

1
2
3
4
5
6
7


func sortedSquares(nums []int) []int {
    for i := range nums {
        nums[i] = nums[i] * nums[i]
    }
    sort.Ints(nums)
    return nums
}

时间复杂度：O(n + nlogn) = O(nlogn)；但为了和下面双指针法算法时间复杂度有鲜明对比，记为 O(n + nlogn)

思路二：双指针，省去排序操作；两个指针分别指向给定数组的首尾，由于给定数组是递增的，所以平方后的大值一定在两端；开辟一个结果数组，每次比较首尾两个指针指向元素平方后的值，大值存入结果数组的末尾，大值指针移动，小值指针不变等待下次比较，重复上述步骤直到俩指针错位，返回结果数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func sortedSquares(nums []int) []int {
    leftIdx, rightIdx := 0, len(nums)-1
    res := make([]int, len(nums))
    resIdx := len(res) - 1
    for leftIdx <= rightIdx {
        if nums[leftIdx]*nums[leftIdx] > nums[rightIdx]*nums[rightIdx] {
            res[resIdx] = nums[leftIdx] * nums[leftIdx]
            leftIdx++ // 左指针移动一个单位
        } else {
            res[resIdx] = nums[rightIdx] * nums[rightIdx]
            rightIdx-- // 右指针移动一个单位
        }
        resIdx-- // 结果集指针移动一个单位
    }
    return res
}

时间复杂度为O(n)

长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

给定一个整数数组和一个目标值，找出数组中一个连续子数组，要求其总和要大于等于目标值，且长度要最小，若能找到则返回长度，若找不到返回0

暴力：一个for循环定滑动窗口的起始位置，一个for循环定滑动窗口的终止位置，用两个for循环完成一个不断搜索区间的过程，会超时

双指针（滑动窗口）：用一个for循环和一个内层while循环来不断调节子数组的起始位置和终止位置，从而得出结果；for循环控制子数组终止位置；while循环控制起始位置；若当前窗口值大于等于目标值，则统计长度，起始位置后移一个单位，直到当前窗口值小于目标值退出while循环，进入下一次for循环，终止位置更新，重复上述步骤，直至终止位置到给定数组末尾

注意：结果初始化为给定数组长度加一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func minSubArrayLen(target int, nums []int) int {
    left := 0
    sum := 0
    res := len(nums) + 1
    for right := range nums {
        sum += nums[right]
        for sum >= target {
            length := right - left + 1 // 子数组长度
            if length < res {
                res = length
            }
            sum -= nums[left] // 更新子数组和
            left++            // 更新起始位置
        }
    }
    if res == len(nums)+1 {
        return 0 // 没有符合条件的子数组
    }
    return res
}

时间复杂度：O(n)
空间复杂度：O(1)

不要以为for里放一个while就以为是O(n²)，时间复杂度主要是看每一个元素被操作的次数，每个元素在滑动窗口进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)

水果成篮

904. 水果成篮 - 力扣（LeetCode）

给定一个数组，找至多包含两种元素的最长子串，返回其长度

最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。

1
2
3
4
5
6


while j < len(nums):
    判断[i, j]是否满足条件
    while 满足条件：
        不断更新结果(注意在while内更新！)
        i += 1 （最大程度的压缩左边界，使得滑窗尽可能的小）
    j += 1

最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。

1
2
3
4
5
6


while j < len(nums):
    判断[i, j]是否满足条件
    while 不满足条件：
        i += 1 （最保守的压缩左边界，一旦满足条件了就退出压缩左边界的过程，使得滑窗尽可能的大）
    不断更新结果（注意在while外更新！）
    j += 1

最小滑窗是在迭代右移左边界的过程中更新结果，而最大滑窗是在迭代右移右边界的过程中更新结果。

判断滑动窗口内是否满足题设条件有两种选择：

遍历这个滑窗来判断是否满足需要，总时间会退化为O(N²)
选择字典，用空间换时间，总时间为O(N).

用哈希表存储窗口内的数以及出现的次数，若出现的数多于两个，则说明不满足条件；每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么需要不断移动 left，并将 fruits[left] 在哈希表中的值减一，当值减少到 0 时，需要将对应的键值对从哈希表中移除，直到哈希表满足要求为止

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func totalFruit(fruits []int) int {
    left := 0
    res := 0
    countMap := make(map[int]int)
    for right := range fruits {
        countMap[fruits[right]]++
        for len(countMap) > 2 { // 不满足条件
            countMap[fruits[left]]-- // 更新哈希表
            if countMap[fruits[left]] == 0 {
                delete(countMap, fruits[left]) // 删除出现次数为0的元素
            }
            left++ // 左边界后移
        }
        res = max(res, right-left+1) // 更新窗口最大长度
    }
    return res
}

时间复杂度：O(n)，其中 n 是数组 fruits 的长度。
空间复杂度：O(1)，哈希表中最多会有三个键值对，可以看成使用了常数级别的空间

最小覆盖子串

76. 最小覆盖子串 - 力扣（LeetCode）

给定两个字符串，返回第一个字符串中涵盖第二个字符串中所有字符的最小子串，重复字符也必须在子串中出现至少同样次数，如果不存在则返回空字符串

维护一个滑动窗口：右边界不断移动，直到在s中找到覆盖t所有字符的子串，记入结果，不断调整左边界，若仍覆盖，则更新结果，若不覆盖了就调整右边界，直到覆盖了，再更新结果，不断调整左边界，直到右边界遍历结束

用哈希表存储第二个字符串的字符以及出现的次数，其值也表示字符串t中对应字符未出现在子串中的次数；用一个变量统计子串中应出现的字符个数；若查询哈希表得知对应字符出现在哈希表，则在更新哈希表之前检查哈希值是否大于0，若大于0，则说明该字符是有效字符，更新统计子串中应出现的字符个数的变量；若子串中应出现的字符个数为0，则说明满足条件

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


func minWindow(s string, t string) string {
    res := ""
    // 记录t中各字符的次数
    mp := make(map[byte]int)
    // 记录还没有覆盖到的字符个数
    count := len(t)
    // 滑动窗口左边界
    left := 0
    // 遍历t计入字典
    for i := 0; i < len(t); i++ {
        mp[t[i]]++
    }
    // 滑动窗口右边界right遍历s
    for right := range s {
        // 判断字典中是否有该字符
        if _, ok := mp[s[right]]; ok {
            // 判断该字符是否还需要覆盖
            if mp[s[right]] > 0 {
                // 更新计数
                count--
            }
            // 更新字典值
            mp[s[right]]--
        }
        // 已全部覆盖
        for count == 0 {
            // 判断结果集是否为空或当前窗口长度小于结果集
            if len(res) == 0 || right-left+1 < len(res) {
                // 更新结果
                res = s[left : right+1]
            }
            // 判断左边界字符是否在字典中
            if _, ok := mp[s[left]]; ok {
                // 判断该字符是否恰好被覆盖
                if mp[s[left]] == 0 {
                    // 更新计数
                    count++
                }
                // 更新字典值
                mp[s[left]]++
            }
            // 更新左边界
            left++
        }
    }
    return res
}

时间复杂度：$O(n)$，虽然有嵌套循环，但每个字符最多被操作两次，所以整体上仍然是线性的时间复杂度
空间复杂度：$O(m)$

螺旋矩阵 II

59. 螺旋矩阵 II - 力扣（LeetCode）

给定一个正整数 n ，生成一个正方形矩阵，顺时针螺旋排列包含 1 到 n^2 所有元素

本题不涉及具体的算法，就是模拟过程，但却十分考察对代码的掌控能力

注意：

先用给定n除以2求出循环次数，也就是需要转几圈，若给定n为奇数，最后中间会剩一个元素，若给定n为偶数，中间不会剩元素
不断循环直至循环次数为0，每次循环就是一圈，完成四个边的填充，填充时遵循左闭右开的规则，每次转完一圈要更新每个边要填充的元素个数、每圈起始的横纵坐标和本圈目前填充到的横纵坐标
每填充一个元素，元素值就加一
由于循环中会递减n和循环次数，所以最后判断奇偶可以用元素值（循环结束后是n²）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    count := 1                 // 元素值
    loop := n / 2              // 循环次数
    startRow, startCol := 0, 0 // 控制起始位置
    eleCount := n              // 标记每圈每个边要填充的元素个数
    for ; loop > 0; loop-- {
        curRow, curCol := startRow, startCol
        eleCount--
        for ; curCol < eleCount; curCol++ {
            matrix[curRow][curCol] = count // 从左到右填充排
            count++
        }
        for ; curRow < eleCount; curRow++ {
            matrix[curRow][curCol] = count // 从上到下填充列
            count++
        }
        for ; curCol > startCol; curCol-- {
            matrix[curRow][curCol] = count // 从右到左填充排
            count++
        }
        for ; curRow > startRow; curRow-- {
            matrix[curRow][curCol] = count // 从下到上填充列
            count++
        }
        startRow++ // 更新每圈起始位置的排数
        startCol++ // 更新每圈起始位置的列数
    }
    if n%2 == 1 {
        matrix[startRow][startCol] = count
    }
    return matrix
}

螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

给定一个 m 行 n 列的矩阵 matrix ，按照顺时针螺旋顺序返回矩阵中的所有元素

注意：

矩阵中元素不一定是从1开始的，不能用最大元素来计算循环次数，要用元素数来计算循环次数
每遍历完一圈查看一次结果集是否满足条件，若满足直接返回，因为是长方形时，有可能结果集已满足但循环次数还有
从右往左和从左往右遍历时要用偏移量控制
若矩阵只有一列，则直接从上往下遍历后返回，因为不构成一圈，也不能通过最后的中间遍历
若矩阵只有一排，则直接从左往右遍历后返回，因为最后一个元素作为四个边的哪个都不会被遍历，也会导致最后的中间遍历索引越界
最后剩下的中间元素，可以是一排也可能是一列，可以用总排/列数减去已遍历的排/列数来判断

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


func spiralOrder(matrix [][]int) []int {
    row, col := len(matrix), len(matrix[0]) // 矩阵的最大行数和列数
    res := make([]int, 0)
    if col == 1 { // 只有一列
        for i := range matrix {
            res = append(res, matrix[i][0])
        }
        return res
    }
    if row == 1 { // 只有一列
        for i := range matrix[0] {
            res = append(res, matrix[0][i])
        }
        return res
    }
    count := row * col             // 矩阵中元素个数
    n := math.Sqrt(float64(count)) // 求元素个数的平方根
    loop := int(n / 2)             // 圈数（取整）
    curX, curY := 0, 0             // 当前遍历到的位置
    offset := 1                    // 偏移量（前闭后开）
    for loop > 0 {                 // 按圈遍历
        for ; curY < col-offset; curY++ { // 从左到右遍历（该行最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curX < row-offset; curX++ { // 从上到下（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curY >= offset; curY-- { // 从右到左（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curX >= offset; curX-- { // 从下到上（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        loop--   // 更新圈数
        offset++ // 更新偏移量
        curX++   // 更新下一次起始排数
        curY++   // 更新下一次起始列数
        if len(res) == count {
            return res
        }
    }
    if row-2*(offset-1) == 1 {
        for ; len(res) != count; curY++ {
            res = append(res, matrix[curX][curY]) // 遍历中间一排
        }
    } else if col-2*(offset-1) == 1 {
        for ; len(res) != count; curX++ {
            res = append(res, matrix[curX][curY]) // 遍历中间一列
        }
    }
    return res
}

简化：loop的计算和中间值的判断

本题的loop计算与59.螺旋矩阵II算法略微差异，因为存在rows和columns两个维度，loop取min(rows, columns) / 2

中间值的判断：若min(rows, columns)为偶数，则矩阵中间不会剩下值；若min(rows, columns)为奇数，则矩阵中间会剩下一个行或列；判断是行还是列，要看矩阵行数和列数的大小，如果行数大于列数，则中间剩下列，反之中间剩下行

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


func spiralOrder(matrix [][]int) []int {
    row, col := len(matrix), len(matrix[0]) // 矩阵的最大行数和列数
    res := make([]int, 0)
    loop := min(row, col) / 2 // 圈数（取整）
    curX, curY := 0, 0        // 当前遍历到的位置
    offset := 1               // 偏移量（前闭后开）
    for loop > 0 {            // 按圈遍历
        for ; curY < col-offset; curY++ { // 从左到右遍历（该行最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curX < row-offset; curX++ { // 从上到下（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curY >= offset; curY-- { // 从右到左（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        for ; curX >= offset; curX-- { // 从下到上（最后一个不遍历）
            res = append(res, matrix[curX][curY])
        }
        loop--   // 更新圈数
        offset++ // 更新偏移量
        curX++   // 更新下一次起始排数
        curY++   // 更新下一次起始列数
    }
    if min(row, col)%2 == 1 { // 奇数=>中间有剩余
        if row > col { // 排数>列数=>剩余一列
            for ; curX <= row-offset; curX++ { // 遍历中间一列(包括最后一个未被遍历的元素)
                res = append(res, matrix[curX][curY])
            }
        } else { // 剩余一排
            for ; curY <= col-offset; curY++ { // 遍历中间一排(包括最后一个未被遍历的元素)
                res = append(res, matrix[curX][curY])
            }
        }
    }
    return res
}

螺旋遍历二维数组

LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）

本题与上一题基本相同，唯一区别是本题数组可能为空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


func spiralArray(array [][]int) []int {
    if len(array) == 0 {
        return []int{}
    }
    row, col := len(array), len(array[0])
    res := make([]int, 0)
    loop := min(row, col) / 2
    curX, curY := 0, 0
    offset := 1
    for loop > 0 {
        for ; curY < col-offset; curY++ {
            res = append(res, array[curX][curY])
        }
        for ; curX < row-offset; curX++ {
            res = append(res, array[curX][curY])
        }
        for ; curY >= offset; curY-- {
            res = append(res, array[curX][curY])
        }
        for ; curX >= offset; curX-- {
            res = append(res, array[curX][curY])
        }
        curX++
        curY++
        offset++
        loop--
    }
    if min(row, col)%2 == 1 {
        if row > col {
            for ; curX <= row-offset; curX++ {
                res = append(res, array[curX][curY])
            }
        } else {
            for ; curY <= col-offset; curY++ {
                res = append(res, array[curX][curY])
            }
        }
    }
    return res
}

附加

搜索二维矩阵

74. 搜索二维矩阵 - 力扣（LeetCode）

给定一个递增的整数矩阵和目标值，若在矩阵中能找到目标值，则返回 true ，否则返回 false

思路：对每行第一个元素二分查找，找到最后一个小于目标值的元素，该行为目标行；对该行再二分查找

对两个示例分析可以发现，最后一次二分后的right就是最后一个小于目标值的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


func searchMatrix(matrix [][]int, target int) bool {
    // 对第一列二分查找
    left, right := 0, len(matrix)-1
    for left <= right {
        mid := left + (right-left)/2
        if matrix[mid][0] == target {
            return true
        } else if matrix[mid][0] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    // 索引越界
    if right < 0 || right >= len(matrix) {
        return false
    }
    // 对目标行二分查找
    return search(matrix[right], target)
}

// 二分查找
func search(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] == target {
            return true
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

时间复杂度：$O(logm+logn)=O(logmn)$
空间复杂度：$O(1)$

第一个错误的版本

278. 第一个错误的版本 - 力扣（LeetCode）

给定一个整数n，0-n中从某个数开始为错误，该数后面的数到n都为错误，找出第一个错误的数，给定了判断数是否错误的API

思路：二分查找找到错误数若前一个仍为错，则继续向左查找，直到找到第一个错误的数或到首；若中间数不为错，则只需向右继续查找，因为中间不错，则左边一定不会有错

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func firstBadVersion(n int) int {
    left, right := 0, n
    for left <= right {
        mid := left + (right-left)/2
        // 判断是否为错误版本
        if isBadVersion(mid) {
            // 判断是否为第一个错误版本
            if mid != 0 && isBadVersion(mid) {
                right = mid - 1
            }
        } else {
            // 继续向右查找错误版本
            left = mid + 1
        }
    }
    return left
}

寻找旋转排序数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

给定一个无重复元素的递增数组，该数组向右循环旋转过，返回数组中的最小值

思路：二分查找比较中间值与最后一个元素大小，若中间值大于最后一个元素，说明最小值在右半部分，反之，最小值在左半部分或中间值就是最小值；左边界=右边界时说明只剩一个值，该值为最小值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

寻找旋转排序数组中的最小值 II

154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）

给定一个可能存在重复元素的递增数组，该数组向右循环旋转过，返回数组中的最小值

思路：二分查找比较中间值与最后一个元素大小，若中间值大于最后一个元素，说明最小值在右半部分，反之，最小值在左半部分或中间值就是最小值，若中间值等于最后一个元素，说明存在重复元素，则右边界前移一个单位；左边界=右边界时说明只剩一个值，该值为最小值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

搜索旋转排序数组

33. 搜索旋转排序数组 - 力扣（LeetCode）

给定一个无重复元素的递增数组和目标值，该数组向右循环旋转过，返回数组中目标值的下标，不存在返回-1

思路：先二分找最小值下标（轴点），再取模正常二分找目标值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func search(nums []int, target int) int {
    // 二分查找最小值索引
    min := findMin(nums)
    // 二分查找目标值
    // lr是以最小值为起点不旋转的索引(r可能会越界)
    left, right := min, min-1+len(nums)
    for left <= right {
        mid := left + (right-left)/2
        // i是映射回数组的mid
        i := mid % len(nums)
        if nums[i] == target {
            // 返回i
            return i
        } else if nums[i] > target {
            // 更新r仍用mid
            right = mid - 1
        } else {
            // 更新l仍用mid
            left = mid + 1
        }
    }
    return -1
}
func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

搜索旋转排序数组 II

81. 搜索旋转排序数组 II - 力扣（LeetCode）

给定一个可能存在重复元素的递增数组和目标值，该数组向右循环旋转过，若数组中存在目标值返回true，否则返回false

思路：先二分找最小值下标（轴点），再取模正常二分找目标值。

注意：找轴点时，若最小值重复，要找到旋转前的首个最小值(轴点)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


func search(nums []int, target int) bool {
    // 二分查找最小值索引
    min := findMin(nums)
    // 找第一个min
    if min == 0 && nums[min] == nums[len(nums)-1] {
        // 首和尾相同都是最小值,更新最小值为首的前一个(尾)
        min = len(nums) - 1
    }
    // 从尾向前找第一个最小值(轴点)
    for min != 0 && nums[min-1] == nums[min] {
        // 更新最小值为前一个
        min--
    }
    // 二分查找目标值
    // lr是以最小值为起点不旋转的索引(r可能会越界)
    left, right := min, min-1+len(nums)
    for left <= right {
        mid := left + (right-left)/2
        // i是映射回数组的mid
        i := mid % len(nums)
        if nums[i] == target {
            return true
        } else if nums[i] > target {
            // 更新r仍用mid
            right = mid - 1
        } else {
            // 更新l仍用mid
            left = mid + 1
        }
    }
    return false
}
func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return left
}

附加

字符串的排列

567. 字符串的排列 - 力扣（LeetCode）

给定两个字符串s1和s2，判断s1的排列之一是否为s2的子串

思路：维护一个大小为2的滑动窗口

实现细节：

用两个数组分别记录两个字符串中各字符的个数，若相等，直接返回true
初始化窗口大小为len(s1)，初始化时只移动右边界，此后左右边界同时移动，同时不断更新两个数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func checkInclusion(s1 string, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	cnt1, cnt2 := [26]int{}, [26]int{}
	// 初始化窗口
	for i, v := range s1 {
		cnt1[v-'a']++
		cnt2[s2[i]-'a']++
	}
	if cnt1 == cnt2 {
		return true
	}
	// 遍历s2
	for i := len(s1); i < len(s2); i++ {
		cnt2[s2[i-len(s1)]-'a']--
		cnt2[s2[i]-'a']++
		if cnt1 == cnt2 {
			return true
		}
	}
	return false
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

维护一个无重复元素的滑动窗口

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func lengthOfLongestSubstring(s string) int {
    cnt := [128]bool{}
    left := 0
    res := 0
    // 遍历s
    for right, v := range s {
        // 遇到重复字符
        for cnt[v] {
            // 删除左边界字符
            cnt[s[left]] = false
            // 更新左边界
            left++
        }
        // 记录非重复字符
        cnt[v] = true
        // 更新结果
        res = max(res, right-left+1)
    }
    return res
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

区间和

卡码网：58. 区间和

给定一个整数数组 Array和若干区间，返回该数组在每个指定区间内元素的总和

暴力时间复杂度：，n为元素个数，m为查询次数，每次查询全区间，最坏为$O(n*m)$

前缀和：

p[i]：array[0]到array[i]的和
计算array[3] + array[4] + array[5] = p[5] - p[2]

注意：Go语言中fmt.Scan的读操作效率低，可以使用bufio.Scanner来提升输入性能，避免超时错误

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


package main

import (
    "fmt"
    "bufio"
    "os"
    "strconv"
)

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    // 读取数组长度
    scanner.Scan()
    length, _ := strconv.Atoi(scanner.Text())
    // 读取数组元素
    array := make([]int, length)
    for i := 0; i < length; i++ {
        scanner.Scan()
        array[i], _ = strconv.Atoi(scanner.Text())
    }

    // 原数组上求前缀和
    for i := 1; i < len(array); i++ {
        array[i] += array[i-1]
    }

    // 循环读取区间直到EOF
    var left, right int
    for scanner.Scan() {
        fmt.Sscanf(scanner.Text(), "%d %d", &left, &right)
        // 判断区间左端是否为0
        if left == 0 {
            // 区间左端为0直接输出前缀和
            fmt.Println(array[right])
        } else {
            // 用前缀和求区间和
            fmt.Println(array[right]-array[left-1])
        }
    }
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

开发商购买土地

卡码网：44. 开发商购买土地

给定一个矩形区域，返回将该区域分为两部分的最小差值

逐行划分、逐列划分，不断比较求得最小结果

求差值可用sum-2*a：a+b=c=>b=c-a=>a-b = a-c+a = 2a - c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62


package main

import (
    "fmt"
    "math"
)

func main() {
    // 读取矩形长宽
    var n, m int
    fmt.Scanln(&n, &m)
    // 读取矩形
    array := make([][]int, n)
    for i := range array {
        array[i] = make([]int, m)
    }
    sum := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Scan(&array[i][j])
            sum += array[i][j]
        }
    }
    res := math.MaxInt32
    count := 0
    // 按行切分
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            count += array[i][j]
            // 判断是否到行尾
            if j == m-1 {
                // 求得从当前行切分的差值
                res = min(res, max(sum, 2*count)-min(sum, 2*count))
            }
        }
    }
    count = 0
    // 按列切分
    for j := 0; j < m; j++ {
        for i := 0; i < n; i++ {
            count += array[i][j]
            // 判断是否到列尾
            if i == n-1 {
                // 求得从当前列切分的差值
                res = min(res, max(sum, 2*count)-min(sum, 2*count))
            }
        }
    }
    fmt.Println(res)
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
} 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

有多少小于当前数字的数字

1365. 有多少小于当前数字的数字 - 力扣（LeetCode）

给定一个数组，对于其中每个元素，统计数组中比它小的元素的个数

思路：

复制一份原数组进行排序，用哈希存储排序后数组每个元素前面有多少个元素；
由于哈希key的唯一性，从后向前遍历排序后数组，可以保证遇到重复元素时记录到最左边元素前的元素个数
遍历原数组，在哈希中查询得到该元素前的元素个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func smallerNumbersThanCurrent(nums []int) []int {
    // 复制原数组
    temp := make([]int, len(nums))
    copy(temp, nums)
    // 数组排序
    sort.Ints(temp)
    // 初始化哈希表
    mp := make(map[int]int)
    // 倒序遍历排序后数组
    for i := len(temp) - 1; i >= 0; i-- {
        // 哈希表存储k:元素 v:比该元素小的元素个数
        mp[temp[i]] = i
    }
    // 遍历原数组
    for i := 0; i < len(nums); i++ {
        // 直接在原数组上存储比当前元素小的元素个数
        nums[i] = mp[nums[i]]
    }
    return nums
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

有效的山脉数组

941. 有效的山脉数组 - 力扣（LeetCode）

给定一个数组，判断其是否为山脉数组

山脉数组：数组长度大于等于3，有一个顶点，严格递增到顶点(无重复)，从顶点开始严格递减

思路一：状态切换

数组长度小于3，返回false
用一个变量记录是否为上升态，初始化为上升态，若上升态遇到当前元素等于下一元素，返回false
直到当前元素大于下一个元素，判断是否从索引0就切换，若是，说明单调减，返回false，若不是，变为非上升态
若非上升态遇到当前元素小于等于下一个元素，返回false
遍历结束后判断上升态是否持续到最后一个元素，若是，说明单调增，返回false
最后返回true

注意：判断单调情况

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


func validMountainArray(arr []int) bool {
    // 判断数组长度是否小于3
    if len(arr) < 3 {
        return false
    }
    // 初始化为上升态
    isInc := true
    // 遍历数组
    i := 0
    for ; i < len(arr)-1; i++ {
        // 判断当前元素是否等于下一元素
        if arr[i] == arr[i+1] {
            return false
        }
        // 判断是否为上升态
        if isInc {
            // 判断当前元素是否大于下一元素
            if arr[i] > arr[i+1] {
                // 判断是否从索引0就切换为非上升态
                if i == 0 {
                    return false
                }
                // 切换为非上升态
                isInc = false
            }
        } else {
            // 判断当前元素是否小于下一元素
            if arr[i] < arr[i+1] {
                return false
            }
        }
    }
    // 判断上升态是否持续到最后一个元素
    if isInc {
        return false
    }
    return true
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

思路二：双指针

用两个指针分别指向数组首尾
若左指针指向元素小于后一元素，则后移一个单位；若右指针指向元素小于前一元素，则前移一个单位
若左右指针在非首尾位置相遇，则返回true；若在首尾处相遇说明是单调，返回false

注意：不能在一个循环中同时移动左右指针并且判断是否相遇，因为在非山脉的情况下，左右指针永远不会相遇，导致进入死循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func validMountainArray(arr []int) bool {
    if len(arr) < 3 {
        return false
    }
    // 初始化左右指针分别指向首尾
    left, right := 0, len(arr)-1
    // 移动左指针到最终位置
    for left != len(arr)-1 && arr[left] < arr[left+1] {
        left++
    }
    // 移动右指针到最终位置
    for right != 0 && arr[right] < arr[right-1] {
        right--
    }
    // 判断左右指针是否相遇且在非首尾处
    if left == right && left != len(arr)-1 && right != 0 {
        return true
    }
    return false
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

独一无二的出现次数

1207. 独一无二的出现次数 - 力扣（LeetCode）

给定一个整数数组，若数组中每个数的出现次数都是独一无二的，则返回 true；否则返回 false

思路：遍历数组，用字典记录出现次数；最后遍历字典值，用另一字典记录是否有重复，若遇到重复出现的，则返回false，遍历结束返回true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func uniqueOccurrences(arr []int) bool {
    mp1 := make(map[int]int)
    mp2 := make(map[int]bool)
    // 遍历给定数组统计每个数的出现次数
    for _, v := range arr {
        mp1[v]++
    }
    // 遍历字典检查出现次数是否重复
    for _, v := range mp1 {
        // 判断是否在字典中已出现该次数
        if mp2[v] {
            return false
        }
        // 标记该次数出现过
        mp2[v] = true
    }
    return true
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

由于题目给定了数组大小和元素值范围，所以可以用数组做哈希

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func uniqueOccurrences(arr []int) bool {
    // 统计次数
    mp1 := [2001]int{}
    // 标记是否出现过
    mp2 := [1001]bool{}
    // 遍历给定数组统计每个数的出现次数
    for _, v := range arr {
        mp1[v+1000]++
    }
    // 遍历字典检查出现次数是否重复
    for _, v := range mp1 {
        // 判断是否在字典中已出现该次数
        if v != 0 && mp2[v] {
            return false
        }
        // 标记该次数出现过
        mp2[v] = true
    }
    return true
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

轮转数组

189. 轮转数组 - 力扣（LeetCode）

给定一个整数数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

思路一：暴力

新开辟一个数组，将原数组轮换后的元素值存入新数组，最后把新数组拷贝回原数组

1
2
3
4
5
6
7


func rotate(nums []int, k int) {
	temp := make([]int, len(nums))
	for i, v := range nums {
		temp[(i+k%len(nums))%len(nums)] = v
	}
	copy(nums, temp)
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

思路二：原地轮转

将被轮转替换的元素交换到未排定数组首保存，每次都将当前操作元素与未排定数组首交换

注意：当轮转后元素为未排定的数组首时，说明未排定元素首和当前操作元素都已排定，无需轮换，只更新当前操作元素与未排定数组首即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func rotate(nums []int, k int) {
    // 当前操作的元素索引
    cur := 0
    // 未排定的数组首
    temp := 0
    // 循环len(nums)次保证每个元素都轮转
    for i := 0; i < len(nums); i++ {
        // 轮转后的索引
        after := (cur + k) % len(nums)
        // 判断轮转后元素是否为未排定的数组首
        if after == temp {
            // 更新当前操作元素为未排定的数组首下一个元素
            cur = after + 1
            // 更新未排定的数组首
            temp++
            // 跳过本次循环后续
            continue
        }
        // 被替换元素放至未排定的数组首
        nums[temp], nums[after] = nums[after], nums[temp]
        // 更新当前操作的元素索引
        cur = after
    }
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

思路三：反转

反转整个字符串
反转区间为前k的子串
反转区间为k到末尾的子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func rotate(nums []int, k int) {
    // 约束k不越界
    k = k % len(nums)
    // 整体反转
    reverse(nums)
    // 反转前k
    reverse(nums[:k])
    // 反转k到末尾
    reverse(nums[k:])
}
func reverse(nums []int) {
    for left, right := 0, len(nums)-1; left < right; left, right = left+1, right-1 {
        nums[left], nums[right] = nums[right], nums[left]
    }
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

给定一个整数数组，返回中心下标，中心下标左侧所有元素相加的和等于右侧所有元素相加的和，若不存在中心下标，则返回 -1

思路一：先统计出前i位的和，最后遍历数组，用前i位总和减去第i位元素值得到左侧所有元素和，用所有元素和减去前i位总和得到右侧所有元素和，若相等，则说明找到中心下标，直接返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func pivotIndex(nums []int) int {
    sum := make([]int, len(nums))
    // 统计前i位的和
    sum[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        sum[i] = sum[i-1] + nums[i]
    }
    // 遍历给定数组和总和数组
    for i, v := range nums {
        // 判断当前元素之前的所有元素和是否等于之后的所有元素和
        if sum[i]-v == sum[len(sum)-1]-sum[i] {
            // 返回当前索引
            return i
        }
    }
    return -1
}

时间复杂度：$O(n)$
空间复杂度：$O(n)$

思路二：先统计出总和，最后遍历数组，逐个累加得到前i位总和，同时用总和减去前i位总和再加上当前元素值得到包括第i位在内的之后所有元素和若相等，则说明当前索引为中心下标，直接返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


func pivotIndex(nums []int) int {
    sum := 0
    // 统计总和
    for _, v := range nums {
        sum += v
    }
    leftSum := 0
    // 遍历给定数组
    for i, v := range nums {
        leftSum += v
        rightSum := sum - leftSum + v
        // 判断前i位所有元素和是否等于包括第i位在内的之后的所有元素和
        if leftSum == rightSum {
            // 返回当前索引
            return i
        }
    }
    return -1
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$

按奇偶排序数组 II

922. 按奇偶排序数组 II - 力扣（LeetCode）

给定一个非负整数数组，其中一半整数是奇数，一半整数是偶数；对数组进行排序，以便当nums[i]为奇数时，i也是奇数；当nums[i]为偶数时，i也是偶数

思路：遍历所有偶数位，若遇到奇数，则在奇数位中找到一个偶数交换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func sortArrayByParityII(nums []int) []int {
    // 标记目前遍历到的奇数位
    oddIdx := 1
    // 遍历偶数位
    for i := 0; i < len(nums); i += 2 {
        // 判断是否为奇数
        if nums[i]%2 != 0 {
            // 遍历奇数位找到一个偶数
            for nums[oddIdx]%2 != 0 {
                oddIdx += 2
            }
            // 交换
            nums[i], nums[oddIdx] = nums[oddIdx], nums[i]
        }
    }
    return nums
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$