双指针算法学习记录

双指针算法学习记录1 剑指 offer 57. 和为 s 的两个数字1.1 解法一暴力解法1.2 解法二双指针算法2 LeetCode 15. 三数之和2.1 解法一排序 暴力枚举 利用 set 去重2.2 解法二排序 双指针3. LeetCode 18. 四数之和3.1 解法一排序 枚举 set 去重3.2 解法二排序 双指针1 剑指 offer 57. 和为 s 的两个数字由于 leetcode 和 剑指 offer 合作终止所以目前无法在网上找到可以在线 OJ 的题目1.1 解法一暴力解法解法核心利用双循环进行枚举列举出所有可能性从而去和 s 进行匹配时间复杂度为O(n^2)且这种解题方法时间超限故不详细展开1.2 解法二双指针算法解法核心将数组首部元素作为头指针left末位元素作为尾指针right因为数组为升序当leftright与 s 进行比较就有三种结果大于 s 则说明尾指针应该向左移动使指向的元素变小去寻找相加等于 s 的元素小于 s 则说明头指针应该向有移动使指向的元素变大等于 s 直接返回下标即可始终不要忘记数组是升序的这是一个关键条件2 LeetCode 15. 三数之和2.1 解法一排序 暴力枚举 利用 set 去重解法核心使用三循环进行暴力枚举时间复杂度为O ( n 3 ) O(n^3)O(n3)将数组排序从而可以使原先例如 [0, -1, 1]、[-1, 0, 1]这种重复只是参数位置不同的数组变为一样的数组最后利用 set 的性质进行去重暴力解法不细讲2.2 解法二排序 双指针对于有序的数组如果可以使用双指针尽量不要使用二分查找双指针可以使时间复杂度降维解法核心排序的用处同解法一一样首先固定一个指针指向头部数组的首元素接下来就要寻找两个数相加为指针指向元素的相反数那这个问题就可以简化为上面讲过的和为 s 的两个数字所以我们可以把指针往右的区域再看为一个数组然后在这个数组中进行双指针查找从而找到符合的元素。需要注意的细节问题虽然上述的解法核心很简单但是有几个很恶心的细节问题如何去重如何才能不漏去所有的可能不漏问题比较好解决我们先来解决这个如果想要不漏去所有的可能性那么我们在使用双指针找到一种和为元素相反数的可能后就不能停止查找而是缩小区间继续查找解决去重去重相比不漏去可能就比较恶心思考一下如果此时双指针在已经查找和为元素相反数的一种可能是如果left指针向右移动的下一个元素还等于left元素本身那查找还有意义么注定会查找到相同的值所以是没有意义的所以要跳过相同的值双指针区间如此那么对于我们第一个指针固定的元素不也是如此么它如果值重复那么双指针区域始终也在查找和上一轮相反数一样的可能所以一定会导致结果重复所以外部也要跳过相同的值到此为止这道题才算是解答完毕本人作答代码classSolution{public:voidLeft(intleft,intright,vectorintnums){while(nums[left1]nums[left]left1right)left;left;}voidRight(intright,intleft,vectorintnums){while(nums[right-1]nums[right]right-1left)right--;right--;}vectorvectorintthreeSum(vectorintnums){sort(nums.begin(),nums.end());vectorvectorintret;inti0;while(inums.size()-2){intlefti1;intrightnums.size()-1;while(leftright){if(nums[i]nums[left]nums[right]0){ret.push_back({nums[left],nums[right],nums[i]});Left(left,right,nums);Right(right,left,nums);}if(nums[i]nums[left]nums[right]0){Left(left,right,nums);}if(nums[i]nums[left]nums[right]0){Right(right,left,nums);}}while(nums[i1]nums[i]i1nums.size()-2)i;i;}returnret;}};谈谈实现时的踩坑内存超限问题我在一次实现的时候没思考清楚对于重复元素的处理是否还需要额外进行一次自增或者自减导致在重复的位置上进行插入没有思考清楚导致左右边界一起移动在实现中我忽略了左右指针的值的和还需再进行一次比较才能确定移动左边界还是右边界只有当与期望值相等时才能左右边界一起缩限故踩坑3. LeetCode 18. 四数之和3.1 解法一排序 枚举 set 去重就是暴力枚举解法绝对超时不细讲了3.2 解法二排序 双指针在作者看来这道题就是三数之和的promax版本做法和三数之和相差无几我们只要将一个指针固定这道题便坍缩到了求三数之和的维度所以不再做详细讲解恶心的点也和三数之和一样注意去重注意边界本人作答代码classSolution{public:vectorvectorintfourSum(vectorintnums,inttarget){sort(nums.begin(),nums.end());inta0;vectorvectorintret;if(nums.size()4)returnret;while(anums.size()-3){inttarget_atarget-nums[a];intba1;while(bnums.size()-2){longlongtarget_b(longlong)target_a-(longlong)nums[b];intleftb1;intrightnums.size()-1;while(leftright){intsumnums[left]nums[right];if(sumtarget_b)left;if(sumtarget_b)right--;if(sumtarget_b){ret.push_back({nums[left],nums[right],nums[b],nums[a]});left;right--;}while(left-1!bnums[left]nums[left-1]leftright)left;while(right1nums.size()-1nums[right]nums[right1]rightleft)right--;}b;while(b-1!anums[b]nums[b-1]bnums.size()-2)b;}a;while(nums[a]nums[a-1]anums.size()-3)a;}returnret;}};事实证明作者还是太年轻了把题想简单了踩了不少坑在双指针内部leftright等于期望值时没有对left和right指针进行调整接下来踩的坑恶心程度以至于作者觉得用一大段篇幅来讲解首先是对于边界检查更加严格2020 年时这道题的测试用例为 292 个2026 年为 294 个多出来的两个测试用例正好对应了两个边界检查。1. 对于 left 和 right 增加的边界检查新增的 测试用例特地检查了left与b相等的情况如果在nums[left]和nums[b]相等的情况下会陷入判断为重复情况跳过重复的元素这样nums[left]就会少一次判断就会少一个正确结果所以在这里我们要添加和b比较是否相等while (left - 1 ! b nums[left] nums[left - 1] left right)right的情况是一样的我们要与nums.size()进行比较。2. 解决大数问题这是其中的一个测试用例如果使用int就会报错所以要在这一行存储数据时换为long longlong long target_b (long long)target_a - (long long)nums[b];