数组深入学习感悟

注：本文学习借鉴于《代码随想录》

一.介绍数组

数组是储存在连续内存空间中的相同类型数据的集合

数组名的理解：

数组名就是数组⾸元素(第⼀个元素)的地址是对的，但是有两个例外：

sizeof(数组名)，sizeof中单独放数组名，这⾥的数组名表⽰整个数组，计算的是整个数组的⼤⼩，

单位是字节

&数组名，这⾥的数组名表⽰整个数组，取出的是整个数组的地址（整个数组的地址和数组⾸元素

的地址是有区别的）

除此之外，任何地⽅使⽤数组名，数组名都表⽰⾸元素的地址

数组中的元素不能删除，只能覆盖。

二.数组解题法

下面我们介绍数组解决问题的几大方法。

1.二分查找

适用类型：对于数组中在范围查找元素的位置，求解平方根，以及插入元素等。

使用前提：二分查找使用前一定要观察元素是否已排好位置

二分查找主要有以下两种写法：

1.1.左闭右闭[left,right]

该写法注意点：（本文不再进行基础实现讲解，可以翻看我的之前文章，有实现过程）

1.while (left <= right) 要使⽤ <= ，因为 left == right 是有意义的，所以使⽤ <=

2.if (nums[middle] > target) right 要赋值为 middle - 1 ，因为当前这个 nums[middle] ⼀定不是 target ，那么接下来要查找的左区间结束下标位置就是 middle - 1

对于leedcode这题：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

就是典型的第一类写法

下面是我对于该题的C语言解法代码：

int search(int* nums, int numsSize, int target) 
{int left=0;int right=numsSize-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;
}

时间复杂度： O(log n)

空间复杂度： O(1)

1.2.左闭右开[left,right)

注意点：

1.while (left < right) ，这⾥使⽤ < , 因为 left == right 在区间 [left, right) 是没有意义的

2.if (nums[middle] > target) right 更新为 middle ，因为当前 nums[middle] 不等于 target ，去左区间继续寻找，⽽寻找区间是左闭右开区间，所以right 更新为 middle ，即：下⼀个查询区间不会去⽐较 nums[middle]。

还是刚才那题，现在我们用第二种方法实现它：

int search(int* nums, int numsSize, int target) 
{int left=0;int right=numsSize;//注意right现在是被赋值为numsSizewhile(left<right){int mid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else if(nums[mid]>target){right=mid;//由于用边界为空，所以right=mid，而不是right=mid-1}else{return mid;}}return -1;
}

补充：如果你想问有没有左开右闭的二分查找，我想说的是有，当使用的意义不大，所以作者这里就不讲了。

下面是推荐的练习题：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台   （69.x 的平⽅根）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台        （367.有效的完全平⽅数）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台           (35.搜索插⼊位置)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台        (34.在排序数组中查找元素的第⼀个和最后⼀个位置)

这些题可能对你有点难，请加油，我相信你一定可以的。

2.双指针法（重点）

解释：双指针法是定义两个有关联的变量，可能是指针，也可能是整数，通过他们实现对数组的操作，使得高效，快捷。

具体的我们来在题目中去感受吧！

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

对于leedcod这题，大家第一反应可能就是暴力出手，疯狂遍历数组，一个for循环不行，那我两个，再不行，再加，但是现在来看看大佬们的思路，让你直呼666……

双指针法就是这题的良方妙药，下面我带着大家用双指针来实现它

由于是数组，我们定义两个整型变量，即slow和fast，表示快慢指针

快指针：寻找新数组的元素 ，新数组就是不含有⽬标元素的数组

慢指针：指向更新新数组下标的位置

看代码：

int removeElement(int* nums, int numsSize, int val) 
{//双指针法int src=0;int dest=0;while(src<numsSize){if(nums[src]!=val){nums[dest++]=nums[src++];}else{src++;}}return dest;
}

是不是大呼学到了。

关于双指针的使用场景，大家需要多做题，自己把握，这样慢慢可能就能感受的啥题目是考察双指针了。

来再带着大家看一题：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

对于这题，我们就直接开始双指针吧！

这题比较特殊，它是有序的，又是问平方，只需要比较负数的平方与整数平方关系即可，大家想想，如果我们定义两个指针，一个指向头，一个指向尾，是不是就可以最快的进行排好序。

看代码实现

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) 
{*returnSize = numsSize;int* arr=(int*)malloc(numsSize*sizeof(int));int n=0;int m=numsSize-1;int c=numsSize-1;while(n<=m){int i=nums[n]*nums[n];int j=nums[m]*nums[m];if(i>j){arr[c--]=i;n++;}else//j>=i{arr[c--]=j;m--;}}return arr;
}

双指针⻛骚起来，也是⽆敌（转自程序员Carl）

下面给大家推荐几道好题：（不用说谢了，这种好东西，一定要拿出来共享，当时快把我写吐了）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

刷完绝对对于双指针有一定的使用感觉了。

3.滑动窗口

如果大家深入了解过数组，就一定听过数组恶魔---滑动窗口

对于滑动窗口，连leedcode上都是中等题起步

下面我们就一题进行了解：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

滑动窗⼝， 就是不断的调节⼦序列的起始位置和终⽌位置，从⽽得出我们要想的结果

我们应该可以看出，如果我们纯暴力来解决这题，就是两个for循环，但是如果用滑动窗口，一个for循环即可，下面来看看实现过程：

⾸先要思考 如果⽤⼀个 for 循环，那么应该表示滑动窗⼝的起始位置，还是终⽌位置。 如果只⽤⼀个for 循环来表示 滑动窗⼝的起始位置，那么如何遍历剩下的终⽌位置？ 此时难免再次陷⼊ 暴⼒解法的怪圈。 所以只⽤⼀个for 循环，那么这个循环的索引，⼀定是表示滑动窗⼝的终⽌位置。

在本题中实现滑动窗⼝，主要确定如下三点：

窗⼝内是什么？

如何移动窗⼝的起始位置？

如何移动窗⼝的结束位置？

窗⼝就是 满⾜其和 ≥ s 的⻓度最⼩的 连续 ⼦数组。

窗⼝的起始位置如何移动：如果当前窗⼝的值⼤于 s 了，窗⼝就要向前移动了（也就是该缩⼩了）。

窗⼝的结束位置如何移动：窗⼝的结束位置就是遍历数组的指针，也就是 for 循环⾥的索引.

看代码实现过程：

int minSubArrayLen(int target, int* nums, int numsSize) 
{int size=0;int result=INT_MAX;int left=0;int sum=0;for(int right=0;right<numsSize;right++){sum+=nums[right];while(sum>=target){size=right-left+1;result=result<=size?result:size;sum-=nums[left++];}}return result==INT_MAX?0:result;
}

时间复杂度直接从O（N*N)降到了O(N),可见这种方法的强大。

推荐大家去B站看代码随想录视频，可能理解更加深入。

下面给大家推荐题目吧：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这两题是真的难啊！！！加油

最后，给小编点赞呗kiss！