数组
数组（Array）是最基础的数据结构之一，它是相同类型元素的有序集合，通过索引（下标） 快速访问元素，在内存中占用连续的存储空间。以下从核心特性、Java 代码示例、经典算法题三个方面详解：
数组的核心特性
- 固定长度：一旦初始化，长度不可变（Java 中通过
new初始化时指定长度）。 - 连续内存：元素在内存中连续存储，索引从
0开始，支持 O (1) 时间复杂度的随机访问。 - 同类型元素：数组中所有元素必须是同一数据类型（基本类型或引用类型）。
- 优缺点：
- 优点：随机访问效率高，结构简单。
- 缺点：插入 / 删除元素需移动其他元素（时间复杂度 O (n)），长度固定不灵活。
Java 数组代码示例
1. 数组的初始化与基本操作
public class ArrayDemo {
public static void main(String[] args) {
// 1. 声明并初始化（静态初始化：长度由元素个数决定）
int[] intArray = {1, 2, 3, 4, 5};
String[] strArray = new String[]{"a", "b", "c"};
// 2. 动态初始化（指定长度，元素为默认值：int→0，String→null）
int[] dynamicArray = new int[5]; // 长度5，初始值 [0,0,0,0,0]
// 3. 访问元素（通过索引，O(1) 时间）
System.out.println(intArray[2]); // 输出：3（访问索引2的元素）
// 4. 修改元素
intArray[2] = 10;
System.out.println(intArray[2]); // 输出：10
// 5. 遍历数组
// 方式1：for循环（适合需要索引的场景）
for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i] + " "); // 输出：1 2 10 4 5
}
System.out.println();
// 方式2：增强for循环（适合仅遍历元素，无需索引）
for (int num : intArray) {
System.out.print(num + " "); // 输出同上
}
System.out.println();
// 6. 数组长度（length属性，注意无括号）
System.out.println("数组长度：" + intArray.length); // 输出：5
}
}
2. 数组的插入与删除（需手动实现）
public class ArrayOperation {
// 向数组指定索引插入元素（需扩容复制）
public static int[] insert(int[] arr, int index, int value) {
if (index < 0 || index > arr.length) {
throw new IndexOutOfBoundsException("索引越界");
}
// 创建新数组（长度+1）
int[] newArr = new int[arr.length + 1];
// 复制原数组索引0到index-1的元素
System.arraycopy(arr, 0, newArr, 0, index);
// 插入新元素
newArr[index] = value;
// 复制原数组index到末尾的元素
System.arraycopy(arr, index, newArr, index + 1, arr.length - index);
return newArr;
}
// 从数组删除指定索引的元素
public static int[] delete(int[] arr, int index) {
if (index < 0 || index >= arr.length) {
throw new IndexOutOfBoundsException("索引越界");
}
// 创建新数组（长度-1）
int[] newArr = new int[arr.length - 1];
// 复制原数组索引0到index-1的元素
System.arraycopy(arr, 0, newArr, 0, index);
// 复制原数组index+1到末尾的元素
System.arraycopy(arr, index + 1, newArr, index, newArr.length - index);
return newArr;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
// 插入：在索引2处插入5 → [1,2,5,3,4]
int[] inserted = insert(arr, 2, 5);
// 删除：删除索引3处的元素（3）→ [1,2,5,4]
int[] deleted = delete(inserted, 3);
}
}
数组常见算法题（附解析）
1. 两数之和（LeetCode 1）
题目：给定一个整数数组 nums 和目标值 target，返回两个数的索引，使它们的和为 target。
解法：哈希表优化（时间 O (n)，空间 O (n)）
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("无结果");
}
2. 数组中的第 K 个最大元素（LeetCode 215）
题目：在未排序的数组中找到第 k 个最大的元素（要求时间复杂度优于 O (n log n)）。
解法：快速选择算法（平均时间 O (n)，最坏 O (n²)）
public int findKthLargest(int[] nums, int k) {
k = nums.length - k; // 转换为“第k小”问题（便于快速选择）
int left = 0, right = nums.length - 1;
while (left < right) {
int pivot = partition(nums, left, right);
if (pivot == k) {
break;
} else if (pivot < k) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
return nums[k];
}
// 快速排序分区函数
private int partition(int[] nums, int left, int right) {
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] >= pivot) j--;
nums[i] = nums[j];
while (i < j && nums[i] <= pivot) i++;
nums[j] = nums[i];
}
nums[i] = pivot;
return i;
}
3. 合并两个有序数组（LeetCode 88）
题目：给两个有序整数数组 nums1（长度 m+n，后 n 位为 0）和 nums2（长度 n），合并 nums2 到 nums1 中，使结果有序。
解法：双指针从后向前遍历（避免覆盖，时间 O (m+n)，空间 O (1)）
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
// 若nums2有剩余元素，直接复制到nums1前面
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
4. 移动零（LeetCode 283）
题目：将数组中的所有 0 移动到末尾，保持非零元素的相对顺序。
解法：双指针（一次遍历，时间 O (n)，空间 O (1)）
public void moveZeroes(int[] nums) {
int index = 0; // 记录非零元素的位置
// 第一步：将所有非零元素移到前面
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
// 第二步：剩余位置补0
while (index < nums.length) {
nums[index++] = 0;
}
}
5. 螺旋矩阵（LeetCode 54）
题目：按顺时针螺旋顺序返回矩阵中的所有元素。
解法：模拟边界收缩（时间 O (mn)，空间 O (mn)）
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) return res;
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (true) {
// 左→右
for (int i = left; i <= right; i++) res.add(matrix[top][i]);
if (++top > bottom) break;
// 上→下
for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
if (--right < left) break;
// 右→左
for (int i = right; i >= left; i--) res.add(matrix[bottom][i]);
if (--bottom < top) break;
// 下→上
for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
if (++left > right) break;
}
return res;
}
总结
数组是算法的基础载体，上述题目涵盖了数组的遍历、查找、插入删除、双指针、边界模拟等核心技巧。掌握数组的特性（尤其是随机访问和连续内存的影响），是解决更复杂数据结构（如链表、栈、队列）问题的前提。实际开发中，Java 的 ArrayList 是数组的动态封装，但其底层仍依赖数组实现，理解数组原理有助于更好地使用集合框架。