一文读懂：什么是数组

大家好，我是三叔，很高兴这期又和大家见面了，一个奋斗在互联网的打工人。

什么是数组

Java是一种面向对象的编程语言，提供了许多数据结构来处理和组织数据。其中，数组是一种常见且强大的数据结构，是存放在连续内存空间上的相同类型数据的集合。

数组可以通过下标访问到数组中的值，数组下标从0开始。

在这里插入图片描述

注意点：

数组下标从0开始
数组内存空间的地址是连续的
数组的元素是不能删的，只能覆盖。

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

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：

在这里插入图片描述

二维数组

例如：

int[][] rating = new int[3][4];

二位数组不是一个3*4的连续数组，但是是一组组连续的数组，如下图所示：

在这里插入图片描述

学习总结：

数组常见类型的算法考察：

1. 二分法

正因为数组是连续的内存空间，所以当存在一组数组是连续的，递增或者递减，都可以使用二分查找来找出目标值，读者可以看看笔者写的二分查找法，需要注意左右闭合区间取舍。

示例代码：

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;// 定义区间 【left,right】while(left <= right) {// 计算中间位置，防止溢出，用减法int middle = left + (right - left) / 2;if(nums[middle] > target) {// 目标值小于中间值，在左边right = middle - 1;} else if (nums[middle] < target) {// 目标值大于中间值，在右边left = middle + 1;} else {// 刚好等于中间值，returnreturn  middle;}}return -1;}
}

2. 双指针法

因为数组大小一旦定义，就无法改变，只能覆盖，数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。

所以在需要移除数组中的对象这类问题时，可以考虑双指针去处理，使用一个快慢指针，找出需要移除的目标值，通过移动快的指针取值放进新的数组中。

示例代码：

class Solution {public int removeElement(int[] nums, int val) {int len = nums.length;int slowIndex = 0;// 双指针for(int fastIndex = 0; fastIndex < len; fastIndex++) {if(val != nums[fastIndex]) {nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
}

还有一种就是双向双指针，一个指针从左开始，一个指针从又开始，左到右找出等于目标值的对象，右到左找到不等于目标值的位置，每次用不等于的覆盖等于的位置

示例代码：

//相向双指针法
class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length - 1;while(right >= 0 && nums[right] == val) { //将right移到从右数第一个值不为val的位置right--;} while(left <= right) {if(nums[left] == val) { //left位置的元素需要移除//将right位置的元素移到left（覆盖），right位置移除nums[left] = nums[right];right--;}left++;while(right >= 0 && nums[right] == val) {right--;}}return left;}
}

以上两种解题思路，笔者觉得第一种双向指针对大家来说相对容易理解。

3. 滑动窗口

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

示例代码：

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int left = 0;int result  = Integer.MAX_VALUE;for(int i = 0; i < nums.length; i++) {sum =sum + nums[i];while(sum >= target) {result = Math.min(result, i - left + 1);sum = sum - nums[left];left++;   }}return result==Integer.MAX_VALUE ? 0 : result;} 
}

4. 螺旋旋转数组

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

此题在于找出规律和临界点~

例如：
在这里插入图片描述
输出如下：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

代码示例：

class Solution {public int[][] generateMatrix(int n) {int offset = 1;  // 控制循环次数int[][] res  = new int[n][n];int start = 0;  // 每次循环的开始点(start, start)int count = 1;  // 定义填充数字int i;int j;while (offset <= n / 2) { // 判断边界后，loop从1开始// 从左到右for(j = start; j < n -offset; j++ ) {res[start][j] = count++;}// 右侧从上到下for(i = start; i < n - offset; i++) {res[i][j] = count++;}// 下边从右到左for(;j >= offset; j--) {res[i][j] = count++;   }// 左侧从下到上for(; i >= offset; i--) {res[i][j] = count++; }start++;offset++;}if (n % 2 == 1) {res[start][start] = count;}return res ;}
}

数组常用api总结

计算数组长度

int[] nums = new int[5];
// 数组长度计算
int len = nums.length;

计算数组下标最大值

int[] nums = new int[5];
// 数组下标最大值
int maxIndex= nums.length - 1;

比较两个对象值的最小值

Math.min(len1, len2); // 返回两个值中较小的

上面是笔者在数组结构算法中常用的api总结，由于训练的时候没有idea那么灵活，这些基本方法没有联想功能，硬敲，熟能生巧。