双指针

接雨水最难的不是写代码，而是证明双指针为什么对。本文用「历史轨迹」论证把双指针的正确性彻底钉死，再用单调栈换一个视角重新理解。

454. 四数相加II 链接：力扣454 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 two sum的变形，把数组两两分组之后变成two sum； 看完题解后的想法 —— 实现中遇到的困难 这里最开始看到分组都要两层循环，时间复杂度达到 $O(n^2)$ ，就觉得在查询逻辑里可以不用哈希直接遍历，因为也是两层循环； 但是这个是要考虑数组大小的，原来的数组大小是 $n$ ，分组求和之后就是 $n^2$ ，如果再两层遍历循环这个 $n^2$ 的数组复杂度就是 $O(n^4)$ ； 代码 class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> hash; int cnt = 0; for (int i = 0; i < nums1.size(); i++) { for (int j = 0; j < nums2.size(); j++) { hash[nums1[i] + nums2[j]]++; } } for (int i = 0; i < nums3.size(); i++) { for (int j = 0; j < nums4.size(); j++) { int sum = nums3[i] + nums4[j]; if (hash.count(-sum) != 0) { cnt += hash[-sum]; } } } return cnt; } }; 383. 赎金信 链接：力扣383 文章：代码随想录 状态：✅ 第一想法 类似于异构词，但是只用部分一致； ...

24. 两两交换链表中的节点 链接：力扣24 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 两两交换，头节点也要进入交换，要把这种特殊情况转变为一般情况，所以需要引入dummyHead； 让之后的交换都是某个节点的next和next->next；变成了一般性问题； 还有就是三指针的交换顺序，这里采用标记了最后需要指向的节点降低心智负担； 看完题解后的想法 —— 实现中遇到的困难 dummy.next忘记指向head了； 代码 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* cur = &dummy; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* finalFoward = cur->next->next->next; ListNode* firstMove = cur->next->next; ListNode* secondMove = cur->next; cur->next = firstMove; firstMove->next = secondMove; secondMove->next = finalFoward; cur = cur->next->next; } return dummy.next; } }; 19. 删除链表的倒数第N个节点 链接：力扣19 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法是反转链表，然后从头找过去，然后删除节点再返回来； ...

704. 二分查找 链接：力扣704 文章：代码随想录 视频：B站讲解 状态：✅ 第一想法 二分查找母题； 有闭区间和开区间两种解法： 闭区间：right 初始化为 nums.size()-1 ,是实右边界；在进入 while 循环时就要注意需要判断 left == right；同时每次移动边界都要从已经找到的地方往右或往左移动一步； 开区间：right 初始化为 nums.size() ,是虚右边界；在进入 while 循环时就要注意写 left < right；移动时左边界是 mid+1， 而右边界是 mid； 看完题解后的想法 —— 实现中遇到的困难 采用实变界进入循环的判断忘记了需要判断left == right； 代码 class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size()-1; while (left <= right) { int mid = left + (right-left)/2; if (nums[mid] == target) { return mid; } else if (nums[mid] > target) { right = mid-1; } else { left = mid+1; } } return -1; } }; 27. 移除元素 链接：力扣27 文章：代码随想录 视频：B站讲解 状态：⚠️ 第一想法 第一想法就是维护两个指针，left 找到 val 位置，而 right 从右边找不为val的值，当左右相遇说明找完了； ...