数组深入学习感悟

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.有效的完全平⽅数）

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

2.双指针法（重点）

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

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

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

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;
}

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

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

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

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

3.滑动窗口

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）官网 - 全球极客挚爱的技术成长平台