算法初步学习双指针学习定义双指针并非真的只是指针而是一种算法技巧用两个指针或下标在数组字符串或链表上协同移动减少嵌套循环引用一般有两个写法数组或字符串用两个下标int, left链表用两个结点指针struct Node *a,*b左右指针两个指针从两端向中间移动常用于有序数组比如有序数列找两数之和inttwoSum(inta[],intn,inttarget){intleft0;intrightn-1;while(leftright){intsuma[left]a[right];if(sumtarget){printf(找到: a[%d]%d, a[%d]%d\n,left,a[left],right,a[right]);return1;}elseif(sumtarget){left;// 和太小左指针右移}else{right--;// 和太大右指针左移}}return0;}快慢指针两个指针同向移动速度不同比如删除数组中所有等于val的元素得到一个数组intt(intnums[],intn,intval){intslow0;for(intfast0;fastn;fast){if(nums[fast]!val){nums[slow]nums[fast];slow;// 只有满足条件的slow才会按顺序加1去得到原数组符合条件的数而fast不管符不符合条件都加一}}returnslow;// 新数组长度}链表快慢指针判断链表是否首尾相连structL{intval;structL*next;};boolh(structL*head){structL*slowhead;structL*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;// slow走一步fast走两步如果是个环肯定会有相等的时候fastfast-next-next;if(slowfast){returntrue;}}returnfalse;}滑动窗口用两个指针圈出一个范围让这个范围像窗户一样在数组字符串上滑动去找到要求的答案比如在数组里找到一段连续的数字要求数字总和必须大于等于某个目标值求所有满足条件的所有切法中长度最短的一段intm(inttarget,intnums[],intn){intleft0;intsum0;intminLenn1;for(intright0;rightn;right){// 从数组的第一个数往后加算和第二次for循环的时候就从第二个数往后开始加sumnums[right];while(sumtarget){// 满足条件的全部进入while循环算最少长度intlenright-left1;if(lenminLen)minLenlen;sum-nums[left];// 减去最左边的那个数看看还大与目标值吗left;}}returnminLenn1?0:minLen;}二分法学习二分法的定义每次将目标值和查找区间的中间值进行比较根据结果将查找范围缩小一半直到找到目标元素理解有一个1到100之间的数比如66我现在可以直接猜中间值50对方回答猜小了范围就变成51到100再猜中间数75猜大了范围就变成了51到74以此类推*其实c语言自带了bsearch函数去二分查找但是运用起来参数很多很麻烦代码实列#includestdio.hintmain(){intarr[100];intn;//要输入多少个数字inttarget;//目标数字scanf(%d,n);printf(请按从小到大的顺序输入 %d 个数字用空格隔开: \n,n);for(inti0;in;i){scanf(%d,arr[i]);}scanf(%d,target);//二分法开始intleft0;intrightn-1;intmid;intfound0;while(leftright){midleft(right-left)/2;if(arr[mid]target){printf(找到了,数字 %d 在数组的第 %d 个位置数组下标为 %d。\n,target,mid1,mid);found1;break;}elseif(arr[mid]target){leftmid1;}else{rightmid-1;}}if(found0){printf(没找到数字 %d。\n,target);}return0;}要点注意while (left right)为 不是 , 如果只有一个数或者最后只剩一个数字的时候写成 就无法得出正确结论left 和 right 取得值并不为左右边界数值是左右边界的数组序号为了之后计算出的 mid 放进数组left 和 right 改变时要将mid加减1因为mid已经猜过了写成mid left (right - left) / 2;而不是mid (right left) / 2;可以在right和left都很大的时候让他们的和不至于过大溢出超出了int的最大值注意向下取整了中间值有两个时自动取了小的输入的数组必须为从小到大的数 如果想输入无序的数组 可以在二分法之前加一个冒泡函数之类的让其排序for(inti0;in-1;i){for(intj0;jn-1-i;j){if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}加深理解没有注意要点 3( right left 等于 mid 时) 不能向右取整​ 假设区间为闭区间【5758】要找的数字为57letf 0right 1向上取整 mid1, 即58​ arr[mid] target, 于是 right mid 区间仍然为【01】陷入死循环。-------易错点如果找不到时停在哪里了​ 数字不存在循环结束之后此时 left right , 且 left right 1 此时left停下的地方恰好是这​ 个数字应该插入的位置​ 例如​ 比如数组是 [1, 3, 5, 7]找 4​ 第一次 mid 1指向34 比 3 大mid加1等于2 left 变成 2​ 第二次 mid 2指向54 比 5 小mid减1等于1right 变成 1​ 此时 left right 循环结束 此时left停留的位置arr[2], 就是4应该放的位置如果数字有重复元素时怎么找第一个和最后一个​ 找到目标之后不要用break退出循环定义一个常量记录现在的mid值即下标值方便找位​ 置重复循环mid值也在变化最后根据它的值描述在数列中的位置。要分向左寻找和向右寻找// 向左查找intf(intarr[],intn,inttarget){intleft0;intrightn-1;intans-1;// 用来记录找到的下标-1表示没找到while(leftright){intmidleft(right-left)/2;if(arr[mid]target){ansmid;// 1. 找到了先记录此时的下标rightmid-1;// 2. 别退出继续向左找}elseif(arr[mid]target){leftmid1;}else{rightmid-1;}}returnans;}左闭右开的写法intleft0;intrightn;// 注意这里是 n ,指向最后一个元素后面的位置取不到while(leftright){// 是 intmidleft(right-left)/2;if(arr[mid]target){returnmid;}elseif(arr[mid]target){leftmid1;}else{rightmid;// 这里是 mid不是 mid - 1}}return-1;在左闭右开范围内的是数组元素的下标 取不到右边界right的值左开右闭就是指大于等于left小于right当left和right相等时自然不成立了所以条件是left right因为取不到right的值所以直接让它等于mid因为mid已经取过了也不要mid的值​​