一、理论基础
一维数组
数组是存放在连续内存空间上的相同类型数据的集合。
需要两点注意的是
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
数组的元素是不能删的，只能覆盖。
二维数组
那么二维数组在内存的空间地址是连续的么？
像Java是没有指针的，同时也不对程序员暴露其元素的地址，寻址操作完全交给虚拟机。
所以看不到每个元素的地址情况，这里我以Java为例，也做一个实验。
public static void test_arr() {
int[][] arr = {{1, 2, 3}, {3, 4, 5}, {6, 7, 8}, {9,9,9}};
System.out.println(arr[0]);
System.out.println(arr[1]);
System.out.println(arr[2]);
System.out.println(arr[3]);
}
输出的地址为：
[I@7852e922
[I@4e25154f
[I@70dea4e
[I@5c647e05
这里的数值也是16进制，这不是真正的地址，而是经过处理过后的数值了，我们也可以看出，二维数组的每一行头结点的地址是没有规则的，更谈不上连续。
所以Java的二维数组可能是如下排列的方式：
二、面试考点
-
对于二维数组应该如何遍历效果更快？
先行再列 : rating[0][0]->rating[0][1]->rating[0][2]->rating[0][3]
三、LeetCode题序
- 双指针法（简单）
- 滑动窗口（中等、困难）
704. (简单)二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
- 元素是不重复的
n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
/**
* 提示：使用双/三指针法
*/
class Solution {
public int search(int[] nums, int target) {
//判断异常情况
if(nums[0]>target || nums[nums.length-1]<target) {
return -1;
}
//1.获取头索引i
int i=0;
//2.获取尾索引j
int j=nums.length-1;
//3.计算中间索引mid
int mid=j/2;
//不存在时：i>j
while(i<=j){
if(nums[mid]==target){
return mid;
}
if(nums[mid]>target){
j=mid-1;
}
if(nums[mid]<target){
i=mid+1;
}
mid=(i+j)>>1;
}
return -1;
}
}
27. (简单)移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
-
不要使用额外的数组空间，你必须仅使用
O(1)额外空间并 原地 修改输入数组。 -
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
/**
* 提示：使用双指针法
*/
class Solution {
public int removeElement(int[] nums, int val) {
//用于存储相等元素的个数
int num=0;
//1.循环计算数组中等于val的元素个数，并记录等于val的个数
for(int i=0;i<nums.length;i++){
if(nums[i]==val){
num++;
continue;
}
//2.将不相等的元素在有偏移量的情况下进行前移
if(num!=0){
nums[i-num]=nums[i];
}
}
return nums.length-num;
}
}
977.(简单)有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
/**
* 注意：越小的负数平方越大
* 提示：使用双指针法
*/
class Solution {
public int[] sortedSquares(int[] nums) {
int arr[]=new int[nums.length];
int font=0;
for(int i=0;i<nums.length;i++){
if(nums[nums.length-1-i+font]*nums[nums.length-1-i+font]<nums[font]*nums[font]){
arr[nums.length-1-i]=nums[font]*nums[font];
font++;
}else{
arr[nums.length-1-i]=nums[nums.length-1-i+font]*nums[nums.length-1-i+font];
}
}
return arr;
}
}
209.(中等)长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。找出元素和>=target的子数组中长度最小的，返回最小长度。没有符合的子数组则返回0。
/**
* 提示：使用双指针法-滑动窗口
* 找子数组相当于求头尾指针：for遍历尾指针，再通过while找头指针。
*/
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i=0;
int sum=0;
int result=Integer.MAX_VALUE;
for(int j=0;j<nums.length;j++){
sum+=nums[j];
while(sum>=target){
if(result==Integer.MAX_VALUE || (j-i+1)<result) result=j-i+1;
sum-=nums[i++];
}
}
return result==Integer.MAX_VALUE?0:result;
}
}
59.(中等)螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n方 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
/**
* 提示-循环遍历圈数：n为偶数圈数为n/2。n为奇数圈数为n/2+中间元素
*/
class Solution {
public int[][] generateMatrix(int n) {
//结果数组
int[][] result=new int[n][n];
//第几圈
int start=0;
//需要几圈
int num=n/2;
//元素值
int count=1;
while(start++<=num){
//左->右
for(int i=start-1;i<n-start;i++){
result[start-1][i]=count++;
}
//上->下
for(int i=start-1;i<n-start;i++){
result[i][n-start]=count++;
}
//右->左
for(int i=n-start;i>start-1;i--){
result[n-start][i]=count++;
}
//下->上
for(int i=n-start;i>start-1;i--){
result[i][start-1]=count++;
}
}
if(n%2==1){
result[n/2][n/2]=count++;
}
return result;
}
}
76. (困难)最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
- t中存在重复字符
- 如果s存在这样的子串，我们保证它是唯一答案
/**
* 提示：使用双指针法-滑动窗口
*/
class Solution {
public String minWindow(String s, String t) {
//头尾指针
int i=0,j=0;
//s数组、t数组
char[] arrS = s.toCharArray();
char[] arrT = t.toCharArray();
//滑动子串、t词频数组
int[] arrSCount=new int[128];
int[] arrTCount=new int[128];
for (char arr : arrT) {
arrTCount[arr]++;
}
//滑动子串与t串的匹配度
int buf=0;
//匹配的最小长度
int length=Integer.MAX_VALUE;
//结果字符串
String result="";
while(j<s.length()){
//1.字符不存在
if(arrTCount[arrS[j]]==0){
j++;
continue;
}
//2.字符存在
arrSCount[arrS[j]]++;
if (arrSCount[arrS[j]]<=arrTCount[arrS[j]]) buf++;
//3.匹配度达到要求，缩小头指针寻找局部最优解
if (buf==t.length()){
while (i<s.length()){
//3.1 字符不存在
if(arrTCount[arrS[i]]==0){
i++;
continue;
}
//3.2 字符存在
if (length==Integer.MAX_VALUE || length>j-i+1) {
result=s.substring(i,j+1);
length=j-i+1;
}
arrSCount[arrS[i]]--;
if (arrSCount[arrS[i]]<arrTCount[arrS[i]]){
i++;
buf--;
break;
}
i++;
}
}
j++;
}
if(length==Integer.MAX_VALUE) return "";
return result;
}
}