代码随想录算法训练营 - 数组篇

26-03-02 16:00 26-03-02 16:00

数组理论基础

在 Go 语言中，数组是一个固定长度的、包含相同数据类型元素的序列。与其他语言相比，Go 的数组有几个鲜明的特点，理解这些特点对写出地道的 Go 代码至关重要。

值语义：在 Go 中，数组是值类型。这意味着当你将一个数组赋值给另一个变量，或者将数组传递给一个函数时，会复制整个数组及其所有元素。对新副本的修改不会影响原始数组。这与切片（slice）的引用语义截然不同。
长度是类型的一部分：[5]int 和 [10]int 被视为两种不同的类型。数组的长度在编译期就确定了，且不可更改。
内存布局：数组的元素在内存中是连续存储的，这带来了优异的缓存局部性和访问效率。
可哈希性：由于数组是值类型且长度固定，它是 可比较 的。这意味着像 [16]byte 这样的数组可以直接作为 map 的键（key），这是切片无法做到的。在处理诸如 MD5 或 SHA256 哈希值时，这一特性非常有用。

尽管在业务逻辑中，动态的切片使用得更广泛，但在需要精确控制内存、与 C 语言交互（CGO）、固定缓冲区或作为 map 键等场景下，数组依然具有不可替代的优势。

此外，Go 的泛型功能也在持续进化。在近期的版本（Go 1.23+）中，社区正在积极探索如何更好地支持多维数组和矩阵运算。例如，未来的版本可能会引入新的泛型约束来处理固定大小的多维数组，使得在进行科学计算或图像处理时，既能保证内存连续性，又能享受泛型带来的类型安全。

二分查找

704. 二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

示例 1： 输入：nums = [-1,0,3,5,9,12], target = 9 输出：4 解释：9 出现在 nums 中并且下标为 4

示例 2： 输入：nums = [-1,0,3,5,9,12], target = 2 输出：-1 解释：2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000] 之间。
nums 的每个元素都将在 [-9999, 9999] 之间。

Go 语言实现

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1 // 定义 target 在左闭右闭的区间里，[left, right]
    // 当 left == right，区间 [left, right] 依然有效，所以用 <=
    for left <= right {
        mid := left + (right-left)>>1 // 防止溢出，等同于 (left+right)/2
        if nums[mid] == target {
            return mid // 目标值等于中间值，直接返回下标
        } else if nums[mid] < target { // 目标值大于中间值，说明目标值在右区间，所以左边界移动到 mid+1
            left = mid + 1
        } else { // 目标值小于中间值，说明目标值在左区间，所以右边界移动到 mid-1
            right = mid - 1 
        }
    }
    return -1 // 目标值不在数组中，返回 -1
}

思路解析：使用二分查找的方法，在有序数组中查找目标值。如果目标值等于中间值，直接返回下标。如果目标值大于中间值，说明目标值在右区间，所以左边界移动到 mid+1。如果目标值小于中间值，说明目标值在左区间，所以右边界移动到 mid-1。最后，如果左边界大于右边界，说明目标值不在数组中，返回 -1。

复杂度分析

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

移除元素

27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

用户评测： 评测机将使用以下代码测试你的解法：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解法将会通过。

示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_] 解释：你的函数应该返回 k = 2，并且 nums 中的前两个元素均为 2。

示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_] 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。

Go 语言实现

func removeElement(nums []int, val int) int {
    slow := 0 // 慢指针，指向新数组的下一个位置
    for fast := 0; fast < len(nums); fast++ { // 快指针，遍历数组
        if nums[fast] != val { // 快指针指向的元素不等于 val，说明是新数组的元素
            nums[slow] = nums[fast] // 慢指针指向的位置赋值为快指针指向的元素
            slow++ // 慢指针后移一位，准备指向下一个新数组的元素
        }
    }
    return slow // 慢指针指向的位置就是新数组的长度
}

思路解析：使用快慢指针的方法，快指针遍历数组，慢指针指向新数组的下一个位置。如果快指针指向的元素不等于 val，说明是新数组的元素，就将快指针指向的元素赋值给慢指针指向的位置，然后慢指针后移一位。如果快指针指向的元素等于 val，说明是旧数组的元素，就跳过不赋值，继续遍历下一个元素。最后，慢指针指向的位置就是新数组的长度。

复杂度分析

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

有序数组的平方

977. 有序数组的平方

题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后变为 [0,1,9,16,100]。

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题。

Go 语言实现

func sortedSquares(nums []int) []int {
    left, right := 0, len(nums)-1 // 左指针，指向数组的第一个元素；右指针，指向数组的最后一个元素
    res := make([]int, len(nums)) // 结果数组，用于存储平方后的元素
    for i := len(nums)-1; i >= 0; i-- { // 从数组的最后一个位置开始，从大到小填充结果数组
        if abs(nums[left]) >= abs(nums[right]) { // 比较左右指针指向元素的绝对值
            res[i] = nums[left] * nums[left]
            left++ // 左指针后移一位
        } else {
            res[i] = nums[right] * nums[right]
            right-- // 右指针前移一位
        }
    }
    return res // 返回结果数组
}

// 辅助函数：计算绝对值
func abs(x int) int {
    if x >= 0 {
        return x
    }
    return -x
}

思路解析：使用双指针的方法，左指针指向数组的第一个元素，右指针指向数组的最后一个元素。从数组的最后一个位置开始，从大到小填充结果数组。比较左指针指向的元素和右指针指向的元素的绝对值，将绝对值较大的元素的平方赋值给结果数组的当前位置。最后，返回结果数组。

复杂度分析

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

长度最小的子数组

209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [nums_l, nums_{l+1}, ..., nums_{r-1}, nums_r]，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例 1： 输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2： 输入：target = 4, nums = [1,4,4] 输出：1

提示：

1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4

Go 语言实现

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    minLen := n + 1 // 初始化最小长度为数组长度 + 1
    slow, sum := 0, 0 // 慢指针和子数组当前和
    for fast := 0; fast < n; fast++ {
        sum += nums[fast] // 快指针遍历，增加子数组和
        for sum >= target { // 当子数组和满足条件时，尝试缩小窗口
            if fast-slow+1 < minLen {
                minLen = fast - slow + 1
            }
            sum -= nums[slow] // 慢指针右移，减去左侧元素
            slow++
        }    
    }
    if minLen == n+1 {
        return 0
    }
    return minLen
}

思路解析：使用 滑动窗口（双指针）的方法。快指针（右边界）负责遍历数组并累加和，当总和大于等于 target 时，尝试通过移动慢指针（左边界）来缩小窗口，寻找最小长度。最后判断是否找到了符合条件的子数组。

复杂度分析

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

螺旋矩阵 II

59. 螺旋矩阵 II

题目描述

给你一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。

示例 1： 59. 螺旋矩阵 II 输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]

Go 语言实现

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    left, right := 0, n-1
    top, bottom := 0, n-1
    num, target := 1, n*n
    
    for num <= target {
        // 从左到右
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++
        // 从上到下
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--
        // 从右到左
        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        bottom--
        // 从下到上
        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }
    return matrix
}

思路解析：使用四个边界指针（left, right, top, bottom）来模拟螺旋遍历。按照 左->右、上->下、右->左、下->上 的顺序循环填充。每填充完一条边，相应的边界就向内收缩一位，直到填充完所有 $n^2$ 个数字。

复杂度分析

时间复杂度： $O(n^2)$
空间复杂度： $O(1)$（不计返回矩阵的空间）

数组总结

通过这几道经典的算法题目，我们对数组这种基础数据结构有了更深刻的认识。结合最新的 Go 语言发展，我们可以从以下几个维度进行总结：

双指针（快慢指针、对撞指针）是核心技巧：无论是移除元素、有序数组的平方还是长度最小的子数组，双指针技术都能高效地解决问题，将多层循环简化为单层遍历，体现了用空间换时间的思想。
循环不变量原则：在二分查找和螺旋矩阵中，保持区间的定义一致性至关重要。例如，在二分查找中始终坚持左闭右闭 [left, right] 的区间定义，所有的边界处理都遵循这个规则，可以避免混乱和错误。
Go 数组的底层原理与算法实践的相互印证：
- 在算法题中，我们经常需要预先分配结果数组（如 make([]int, len(nums))），这正好利用了数组连续内存和编译期大小确定的特性，保证了高效的随机访问。
- 值语义 提醒我们，在需要修改集合的场景下，必须使用切片（如题目中的函数参数 nums []int），以避免不必要的内存拷贝。
- 对于多维数组/矩阵，Go 目前的表达方式是 [][]int，这是一种切片嵌套的结构，其内存可能不连续。未来随着泛型的发展，可能会有更高性能的矩阵类型。
语言版本更新的启示：Go 团队一直在努力提升性能。例如，Go 1.24 中对 map 底层引擎的升级，间接提升了以数组作为键的查找效率。而 Go 1.26 对编译器逃逸分析的增强，使得一些切片操作可以被优化为栈上分配，减少了 GC 压力。

总之，数组是数据结构的基石。掌握了对数组的操作，就能更好地理解更复杂的数据结构（如切片、矩阵）。在训练算法思维的同时，也深入理解你所使用的编程语言的底层细节，是一名优秀程序员的必备素养。