算法初步学习

发布时间：2026/10/30 6:47:30
算法初步学习

算法初步学习

双指针学习

定义

双指针并非真的只是指针，而是一种算法技巧，用两个指针或下标在数组字符串或链表上协同移动，减少嵌套循环（引用）

一般有两个写法：

数组或字符串：用两个下标，int, left
链表：用两个结点指针，struct Node *a,*b

左右指针

两个指针从两端向中间移动，常用于有序数组

比如：有序数列找两数之和

inttwoSum(inta[],intn,inttarget){intleft=0;intright=n-1;while(left<right){intsum=a[left]+a[right];if(sum==target){printf("找到: a[%d]=%d, a[%d]=%d\n",left,a[left],right,a[right]);return1;}elseif(sum<target){left++;// 和太小，左指针右移}else{right--;// 和太大，右指针左移}}return0;}

快慢指针

两个指针同向移动速度不同

比如：删除数组中所有等于val的元素，得到一个数组

intt(intnums[],intn,intval){intslow=0;for(intfast=0;fast<n;fast++){if(nums[fast]!=val){nums[slow]=nums[fast];slow++;// 只有满足条件的slow才会按顺序加1，去得到原数组符合条件的数，而fast不管符不符合条件都加一}}returnslow;// 新数组长度}

链表快慢指针

判断链表是否首尾相连

structL{intval;structL*next;};boolh(structL*head){structL*slow=head;structL*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;// slow走一步fast走两步，如果是个环肯定会有相等的时候fast=fast->next->next;if(slow==fast){returntrue;}}returnfalse;}

滑动窗口

用两个指针圈出一个范围，让这个范围像窗户一样在数组字符串上滑动，去找到要求的答案

比如：在数组里找到一段连续的数字，要求数字总和必须大于等于某个目标值，求所有满足条件的所有切法中，长度最短的一段

intm(inttarget,intnums[],intn){intleft=0;intsum=0;intminLen=n+1;for(intright=0;right<n;right++){// 从数组的第一个数往后加算和，第二次for循环的时候就从第二个数往后开始加sum+=nums[right];while(sum>=target){// 满足条件的全部进入while循环算最少长度intlen=right-left+1;if(len<minLen)minLen=len;sum-=nums[left];// 减去最左边的那个数看看还大与目标值吗left++;}}returnminLen==n+1?0:minLen;}

二分法学习

二分法的定义

每次将目标值和查找区间的中间值进行比较，根据结果将查找范围缩小一半，直到找到目标元素

理解：有一个1到100之间的数，比如66，我现在可以直接猜中间值50，对方回答猜小了，范围就变成51到100，再猜中间数75，猜大了，范围就变成了51到74，以此类推

*其实c语言自带了bsearch函数去二分查找，但是运用起来参数很多，很麻烦

代码实列

#include<stdio.h>intmain(){intarr[100];intn;//要输入多少个数字inttarget;//目标数字scanf("%d",&n);printf("请按从小到大的顺序输入 %d 个数字（用空格隔开）: \n",n);for(inti=0;i<n;i++){scanf("%d",&arr[i]);}scanf("%d",&target);//二分法开始intleft=0;intright=n-1;intmid;intfound=0;while(left<=right){mid=left+(right-left)/2;if(arr[mid]==target){printf("找到了,数字 %d 在数组的第 %d 个位置（数组下标为 %d）。\n",target,mid+1,mid);found=1;break;}elseif(arr[mid]<target){left=mid+1;}else{right=mid-1;}}if(found==0){printf("没找到数字 %d。\n",target);}return0;}

要点

  1. 注意while (left <= right)为 <= 不是 < , 如果只有一个数或者最后只剩一个数字的时候写成 < 就无法得出正确结论
  2. left 和 right 取得值并不为左右边界数值，是左右边界的数组序号，为了之后计算出的 mid 放进数组
  3. left 和 right 改变时要将mid加减1，因为mid已经猜过了
  4. 写成mid = left + (right - left) / 2;而不是mid = (right + left) / 2;可以在right和left都很大的时候让他们的和不至于过大溢出（超出了int的最大值）
    • 注意向下取整了，中间值有两个时自动取了小的
  5. 输入的数组必须为从小到大的数， 如果想输入无序的数组， 可以在二分法之前加一个冒泡函数之类的让其排序
for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}

加深理解

  1. 没有注意要点 3，( right， left 等于 mid 时) 不能向右取整

​ 假设区间为闭区间【57，58】，要找的数字为57，letf = 0，right = 1，向上取整 mid=1, 即58，

​ arr[mid] > target, 于是 right = mid ，区间仍然为【0，1】，陷入死循环。-------易错点

  1. 如果找不到时，停在哪里了

​ 数字不存在，循环结束之后，此时 left > right , 且 left = right + 1， 此时left停下的地方恰好是这

​ 个数字应该插入的位置

​ 例如：

​ 比如数组是 [1, 3, 5, 7]，找 4

​ 第一次 mid = 1（指向3），4 比 3 大，mid加1等于2， left 变成 2

​ 第二次 mid = 2（指向5），4 比 5 小，mid减1等于1，right 变成 1

​ 此时 left > right 循环结束， 此时left停留的位置arr[2], 就是4应该放的位置

  1. 如果数字有重复元素时，怎么找第一个和最后一个

​ 找到目标之后，不要用break退出循环，定义一个常量记录现在的mid值，即下标值，方便找位

​ 置，重复循环，mid值也在变化，最后根据它的值描述在数列中的位置。要分向左寻找和向右寻找

// 向左查找intf(intarr[],intn,inttarget){intleft=0;intright=n-1;intans=-1;// 用来记录找到的下标，-1表示没找到while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==target){ans=mid;// 1. 找到了，先记录此时的下标right=mid-1;// 2. 别退出，继续向左找}elseif(arr[mid]<target){left=mid+1;}else{right=mid-1;}}returnans;}

  1. 左闭右开的写法

    intleft=0;intright=n;// 注意这里是 n ,指向最后一个元素后面的位置，取不到while(left<right){// 是 <intmid=left+(right-left)/2;if(arr[mid]==target){returnmid;}elseif(arr[mid]<target){left=mid+1;}else{right=mid;// 这里是 mid，不是 mid - 1}}return-1;

在左闭右开范围内的是数组元素的下标， 取不到右边界right的值

左开右闭就是指大于等于left小于right，当left和right相等时自然不成立了，所以条件是left < right

因为取不到right的值，所以直接让它等于mid，因为mid已经取过了，也不要mid的值

​

​