数组(Array)

基本特性 #

一维数组 #

数组常被用来当做栈、堆和队列的容器,除此之外,大多是单纯只涉及数组的题目。

特点:

  1. 支持下标
  2. 支持切片
  3. 有固定长度或可变长度

二维数组 #

JavaScript #

var arr = new Array(10); //表格有10行
for(var i = 0;i < arr.length; i++){
 arr[i] = new Array(10).fill(0); //每行有10列
}

Golang #

package main

import "fmt"

func main() {
    // Step 1: 创建数组
    values := [][]int{}

    // Step 2: 使用 append() 函数向空的二维数组添加两行一维数组
    row1 := []int{1, 2, 3}
    row2 := []int{4, 5, 6}
    values = append(values, row1)
    values = append(values, row2)

    // Step 3: 显示两行数据
    fmt.Println("Row 1")
    fmt.Println(values[0])
    fmt.Println("Row 2")
    fmt.Println(values[1])

    // Step 4: 访问第一个元素
    fmt.Println("第一个元素为:")
    fmt.Println(values[0][0])
}
//Row 1
//[1 2 3]
//Row 2
//[4 5 6]
//第一个元素为:
//1

应用场景 #

数组结构很简单,但是出的题涉及的算法类型比较多,比如排序、二分法、双指针、滑动窗口,还会有一些是动态规划。

常用技巧 #

双指针 #

双指针还有快慢指针和左右指针的区别,这里基本都是左右指针,快慢指针一般会应用在循环链表的数据结构里。

剑指 Offer II 006. 排序数组中两个数字之和

剑指 Offer II 007. 数组中和为 0 的三个数

26. 删除有序数组中的重复项

var removeDuplicates = function(nums) {
    const n = nums.length;
    if (n === 0) {
        return 0;
    }
    let fast = 1, slow = 1;
    while (fast < n) {
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
};

滑动窗口 #

双指针的进阶方案就是滑动窗口,两种方案的思路差不多。

剑指 Offer II 008. 和大于等于 target 的最短子数组

二分查找 #

双指针只能逐个遍历,如果算法本身就需要是排序数组,还可以考虑是否可以用二分查找解决,效率会更高。

如果是求连续子数组的问题,很显然不能进行排序。

前缀和 #

前缀和指一个数组的某下标之前的所有数组元素的和(包含其自身)。前缀和分为一维前缀和,以及二维前缀和。前缀和是一种重要的预处理,能够降低算法的时间复杂度。多数时候还需要考虑配合散列表一起,是比较巧妙的解法。

剑指 Offer II 009. 乘积小于 K 的子数组

剑指 Offer II 010. 和为 k 的子数组

func subarraySum(nums []int, k int) int {
    count, pre := 0, 0
    m := map[int]int{}
    m[0] = 1
    for i := 0; i < len(nums); i++ {
        pre += nums[i]
        if _, ok := m[pre - k]; ok {
            count += m[pre - k]
        }
        m[pre] += 1
    }
    return count
}

剑指 Offer II 011. 0 和 1 个数相同的子数组

剑指 Offer II 012. 左右两边子数组的和相等