跳到主要内容

数组

数组是最基础的数据结构，它用一段连续的内存空间存储相同类型的元素。正是因为"连续"这个特性，数组拥有了 O(1)O(1) 的随机访问能力，但也付出了插入删除效率较低的代价。

数组的核心特性​

为什么数组能随机访问？​

计算机内存是线性的，每个存储单元都有唯一的地址。数组申请到一块连续内存后，知道了起始地址（基地址），就能通过简单的数学计算得到任意元素的地址：

Location(i)=BaseAddress+i×ElementSizeLocation(i) = BaseAddress + i \times ElementSize

比如一个 int 数组，基地址为 1000，每个 int 占 4 字节。那么 arr[5] 的地址就是 1000+5×4=10201000 + 5 \times 4 = 1020。这就是为什么数组下标从 0 开始：下标本质上是"偏移量"，第一个元素的偏移量是 0。

优缺点分析​

优点：

  • 随机访问 O(1)O(1)：这是数组最大的优势
  • 缓存友好：连续内存让 CPU 缓存预取更高效
  • 空间紧凑：没有额外的指针开销

缺点：

  • 大小固定：静态数组创建后无法改变大小
  • 插入删除 O(n)O(n)：需要移动后续元素
  • 内存要求高：需要连续的大块内存

缓存局部性原理​

现代 CPU 有多级缓存，读取内存时会一次性加载一个"缓存行"（通常是 64 字节）。当访问 arr[i] 时，arr[i+1]、arr[i+2] 等邻近元素很可能也被加载到缓存中。这意味着顺序遍历数组比随机访问或遍历链表快得多。

这就是为什么在实际编程中，"对数据的访问顺序"会极大地影响性能。

数组的基本操作​

静态数组实现​

public class Array {
    private int[] data;
    private int size;  // 当前元素个数
    
    public Array(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
    }
    
    // 随机访问 - O(1)
    public int get(int index) {
        checkIndex(index);
        return data[index];
    }
    
    // 修改元素 - O(1)
    public void set(int index, int value) {
        checkIndex(index);
        data[index] = value;
    }
    
    // 在末尾添加 - O(1)（如果不需要扩容）
    public void append(int value) {
        if (size == data.length) {
            throw new IllegalStateException("Array is full");
        }
        data[size++] = value;
    }
    
    // 在指定位置插入 - O(n)
    public void insert(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (size == data.length) {
            throw new IllegalStateException("Array is full");
        }
        // 从后向前移动元素，为新元素腾出位置
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
    }
    
    // 删除指定位置元素 - O(n)
    public int remove(int index) {
        checkIndex(index);
        int removed = data[index];
        // 从前向后移动元素，填补空缺
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        return removed;
    }
    
    // 查找元素 - O(n)
    public int indexOf(int value) {
        for (int i = 0; i < size; i++) {
            if (data[i] == value) return i;
        }
        return -1;
    }
    
    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

动态数组实现​

动态数组在容量不足时自动扩容，是实际应用中最常用的数组形式。Java 的 ArrayList、Python 的 list 都是动态数组。

public class DynamicArray<E> {
    private Object[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    public DynamicArray() {
        this.data = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    // 添加元素 - 均摊 O(1)
    public void add(E element) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[size++] = element;
    }
    
    // 在指定位置插入 - O(n)
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (size == data.length) {
            resize(data.length * 2);
        }
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = element;
        size++;
    }
    
    // 删除元素 - O(n)
    @SuppressWarnings("unchecked")
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        E removed = (E) data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;  // 帮助垃圾回收
        
        // 缩容：元素少于容量的 1/4 时
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        return removed;
    }
    
    @SuppressWarnings("unchecked")
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (E) data[index];
    }
    
    private void resize(int newCapacity) {
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
    
    public int size() { return size; }
    public boolean isEmpty() { return size == 0; }
}

扩容策略分析：

为什么选择 2 倍扩容？设扩容倍数为 kk，每次扩容的成本是 O(n)O(n)。如果我们进行 nn 次添加操作，扩容会发生在第 kk、k2k^2、k3k^3... 次操作时。将这些扩容成本均摊到每次操作，得到均摊时间复杂度为 O(1)O(1)。

为什么缩容阈值是 1/4 而不是 1/2？如果在 1/2 处缩容，之后立刻添加元素又会触发扩容，造成"复杂度震荡"。

二维数组与内存布局​

二维数组在逻辑上是"表格"，但在物理内存中仍然是线性的。这就涉及到如何将二维映射到一维的问题。

行优先存储 vs 列优先存储​

行优先存储：先存储第一行的所有元素，再存储第二行，依此类推。

二维数组:          行优先存储:
[1, 2, 3]         内存: [1, 2, 3, 4, 5, 6]
[4, 5, 6]                ↑第一行  ↑第二行

地址计算公式：offset=row×NCOLS+coloffset = row \times NCOLS + col

列优先存储：先存储第一列的所有元素，再存储第二列，依此类推。

二维数组:          列优先存储:
[1, 2, 3]         内存: [1, 4, 2, 5, 3, 6]
[4, 5, 6]                ↑第一列 ↑第二列 ↑第三列

地址计算公式：offset=col×NROWS+rowoffset = col \times NROWS + row

不同语言的选择​

语言存储顺序
C/C++、Java、Python行优先
Fortran、MATLAB、R列优先

性能影响​

理解内存布局对性能至关重要。遍历二维数组时，应该按照内存存储的顺序访问：

// 行优先存储时的正确遍历方式（快）
for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        arr[i][j] = ...;  // 连续访问内存
    }
}

// 行优先存储时的错误遍历方式（慢）
for (int j = 0; j < cols; j++) {
    for (int i = 0; i < rows; i++) {
        arr[i][j] = ...;  // 跳跃访问，缓存命中低
    }
}

性能差异可达数倍甚至数十倍，取决于数组大小和 CPU 缓存。

稀疏数组​

当二维数组中大部分元素为相同值（通常是 0 或 null）时，称为稀疏数组。直接存储会浪费大量空间，可以采用压缩存储。

压缩方式​

只存储非零元素的坐标和值。通常用三元组表示：(行, 列, 值)

// 原始二维数组（稀疏）
int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1;  // 黑子
chessBoard[2][3] = 2;  // 白子
// 其余都是 0

// 压缩存储
// 第一行记录：总行数、总列数、非零元素个数
// 后续行记录：行、列、值
int[][] sparse = {
    {11, 11, 2},  // 11行11列，2个非零元素
    {1, 2, 1},    // (1,2)位置值为1
    {2, 3, 2}     // (2,3)位置值为2
};

稀疏数组的转换​

// 二维数组转稀疏数组
public int[][] toSparse(int[][] arr) {
    // 统计非零元素个数
    int count = 0;
    for (int[] row : arr) {
        for (int val : row) {
            if (val != 0) count++;
        }
    }
    
    // 创建稀疏数组
    int[][] sparse = new int[count + 1][3];
    sparse[0][0] = arr.length;      // 行数
    sparse[0][1] = arr[0].length;   // 列数
    sparse[0][2] = count;           // 非零元素个数
    
    // 填充非零元素
    int idx = 1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (arr[i][j] != 0) {
                sparse[idx][0] = i;
                sparse[idx][1] = j;
                sparse[idx][2] = arr[i][j];
                idx++;
            }
        }
    }
    return sparse;
}

// 稀疏数组还原为二维数组
public int[][] fromSparse(int[][] sparse) {
    int rows = sparse[0][0];
    int cols = sparse[0][1];
    int[][] arr = new int[rows][cols];
    
    for (int i = 1; i < sparse.length; i++) {
        arr[sparse[i][0]][sparse[i][1]] = sparse[i][2];
    }
    return arr;
}

数组高级技巧​

双指针技巧​

双指针是一种在数组上进行高效遍历的技巧，常用于原地去重、反转、快排分区等问题。

类型一：相向双指针（从两端向中间）

// 反转数组 - O(n) 时间，O(1) 空间
public void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

// 两数之和 II（有序数组）
public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

类型二：同向双指针（快慢指针）

// 移除元素（原地移除所有值为 val 的元素）
public int removeElement(int[] nums, int val) {
    int slow = 0;  // 慢指针：下一个有效元素的位置
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

// 原地删除有序数组中的重复项
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 1;  // 慢指针：下一个不重复元素的位置
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

滑动窗口​

滑动窗口是一种处理子数组/子串问题的技巧，它通过维护一个"窗口"，避免重复计算，将 O(n2)O(n^2) 优化到 O(n)O(n)。

核心思想：窗口内的元素满足某些条件，窗口滑动时，利用之前的信息更新结果，而不是重新计算。

固定大小窗口：

// 大小为 k 的子数组的最大和
public int maxSumSubarray(int[] arr, int k) {
    // 先计算第一个窗口的和
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    int maxSum = windowSum;
    
    // 滑动窗口：减去左边出去的，加上右边进来的
    for (int i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

可变大小窗口：

// 长度最小的子数组（和 >= target）
public int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];  // 扩展右边界
        
        // 当窗口满足条件时，收缩左边界
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

// 无重复字符的最长子串
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // 如果字符已在窗口中，移动左边界
        if (window.containsKey(c)) {
            left = Math.max(left, window.get(c) + 1);
        }
        window.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

滑动窗口适用场景：

  • 寻找满足条件的最大/最小子数组
  • 子数组/子串相关的问题
  • 连续区间的问题

前缀和​

前缀和是预处理数组的一种技巧，可以在 O(1)O(1) 时间内回答区间求和问题。

// 构建前缀和数组
// prefix[i] 表示 arr[0] 到 arr[i-1] 的和
public int[] buildPrefixSum(int[] arr) {
    int[] prefix = new int[arr.length + 1];
    for (int i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

// 区间 [left, right] 的和
public int rangeSum(int[] prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

应用示例：和为 K 的子数组个数

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);  // 前缀和为 0 出现 1 次
    
    int count = 0, sum = 0;
    for (int num : nums) {
        sum += num;
        // 如果存在前缀和为 sum - k，说明中间有一段和为 k
        if (prefixCount.containsKey(sum - k)) {
            count += prefixCount.get(sum - k);
        }
        prefixCount.put(sum, prefixCount.getOrDefault(sum, 0) + 1);
    }
    return count;
}

差分数组​

差分数组是前缀和的逆运算，用于高效处理区间修改问题。

// 差分数组：diff[i] = arr[i] - arr[i-1]
public int[] getDiffArray(int[] arr) {
    int[] diff = new int[arr.length];
    diff[0] = arr[0];
    for (int i = 1; i < arr.length; i++) {
        diff[i] = arr[i] - arr[i - 1];
    }
    return diff;
}

// 区间 [left, right] 所有元素加 val
public void rangeAdd(int[] diff, int left, int right, int val) {
    diff[left] += val;
    if (right + 1 < diff.length) {
        diff[right + 1] -= val;
    }
}

// 从差分数组还原原数组
public int[] restoreArray(int[] diff) {
    int[] arr = new int[diff.length];
    arr[0] = diff[0];
    for (int i = 1; i < diff.length; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }
    return arr;
}

应用场景：航班预订统计、区间加法等需要对同一区间多次修改的问题。

经典问题​

合并两个有序数组​

// 从后向前合并，避免额外的空间
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;      // nums1 有效元素末尾
    int j = n - 1;      // nums2 末尾
    int k = m + n - 1;  // 合并位置
    
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    // 处理 nums2 剩余元素
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

旋转数组​

// 旋转数组 k 次
public void rotate(int[] nums, int k) {
    k = k % nums.length;  // 处理 k > n 的情况
    
    // 方法一：三次反转
    reverse(nums, 0, nums.length - 1);      // 反转整个数组
    reverse(nums, 0, k - 1);                 // 反转前 k 个
    reverse(nums, k, nums.length - 1);       // 反转剩余部分
}

private void reverse(int[] nums, int left, int right) {
    while (left < right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

螺旋矩阵​

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // 从左到右
        for (int i = left; i <= right; i++) result.add(matrix[top][i]);
        top++;
        // 从上到下
        for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
        right--;
        // 从右到左
        if (top <= bottom) {
            for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
            bottom--;
        }
        // 从下到上
        if (left <= right) {
            for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
            left++;
        }
    }
    return result;
}

小结​

数组是最基础的数据结构，掌握它需要理解：

  1. 核心特性：连续内存带来 O(1)O(1) 随机访问，但也限制了插入删除效率
  2. 动态数组：自动扩容的实现和均摊分析
  3. 内存布局：行优先/列优先对性能的影响
  4. 高级技巧：双指针、滑动窗口、前缀和、差分数组

这些技巧在解决数组相关问题时非常有效，值得深入理解和练习。

练习​

基础：

  1. LeetCode 1：两数之和
  2. LeetCode 88：合并两个有序数组
  3. LeetCode 283：移动零
  4. LeetCode 26：删除有序数组中的重复项

双指针： 5. LeetCode 167：两数之和 II 6. LeetCode 11：盛最多水的容器 7. LeetCode 15：三数之和

滑动窗口： 8. LeetCode 209：长度最小的子数组 9. LeetCode 3：无重复字符的最长子串 10. LeetCode 438：找到字符串中所有字母异位词

前缀和/差分： 11. LeetCode 560：和为 K 的子数组 12. LeetCode 1109：航班预订统计

矩阵： 13. LeetCode 48：旋转图像 14. LeetCode 54：螺旋矩阵 15. LeetCode 73：矩阵置零