6.12-双指针

本文最后更新于 2024年10月21日早上

27. 移除元素

题意描述：

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

思路：

定义快慢指针fast、slow，fast记录新数组元素，slow记录新数组下标。

AC代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
      int slow = 0;
      for(int fast = 0 ; fast < nums.size() ; fast ++){
        if(nums[fast] != val)  nums[slow++] = nums[fast];
      }

      return slow;
    }
};

344.反转字符串

题意描述：

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
提示：
1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

思路：

定义双指针i 从左边开始遍历、j从右边开始遍历，每次交换字符元素。

AC代码：


class Solution{
  public:
        void reverseString(vector<char>& s){
          for(int i = 0 , j = s.size() - 1 ; i < s.size() / 2 ; i ++ , j --)   swap(s[i] , s[j]);
        }
};//函数是void，故不用return

替换数字

题意描述：

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。

思路：

先统计原字符串s中数字的个数cnt ，将s扩容到目标大小，即 s.size() + 5 * cnt，然后定义新旧指针（我这里用的快慢）分别指向新旧字符串数组的最后一个元素，如果遇到数字，新数组倒序输入number,其他情况复制旧数组元素到新数组。

AC代码：

#include<iostream>
using namespace std;

int main(){
  string s;
  cin >> s;
  int  n = s.size(), cnt = 0;
  for(int fast = 0 ; fast < n ; fast++){
    if(s[fast] >= '0' && s[fast] <= '9')  cnt++;
  }
  s.resize( n + 5 * cnt);

  for(int fast = s.size() - 1 , slow = n - 1; slow >= 0 ;slow -- ){
    if(s[slow] >= '0' && s[slow] <= '9'){
      s[fast --] = 'r';
      s[fast --] = 'e';
      s[fast --] = 'b';
      s[fast --] = 'm';
      s[fast --] = 'u';
      s[fast --] = 'n';
    }
    else {
      s[fast --] = s[slow]; 
    }
  }
  cout << s;
}

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

M:151.翻转字符串里的单词

题意描述：

给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
1
2
输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：
1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的原地解法。

思路：

去除多余空格，思路与移除元素相同，val = ‘ ’；
用reverse函数将整个字符串翻转
翻转单词

AC代码：

removeExtraSpaces函数，从去除前面，中间，后面空格的顺序来写。

//版本一 
        void removeExtraSpaces(string& s){
          int slow = 0, fast = 0;
         // 去掉字符串前面的空格
          while(s.size() > 0 && fast < s.size() && s[fast] == ' ')  fast ++;
          // 去掉字符串中间部分的冗余空格
          for( ; fast < s.size() ; fast++){
            if(fast - 1 > 0 && s[fast - 1] == s[fast] && s[fast] == ' ')  continue;
            else  s[slow ++] = s[fast];
          }
          //后面此时最多有一个空格,重新设置字符串大小
          if(slow - 1 > 0 && s[slow - 1] == ' ')  s.resize(slow - 1)
          else s.resize(slow);
        }

// 版本二 
void removeExtraSpaces(string& s){
          int slow = 0;
          for(int fast = 0 ; fast < s.size() ; fast ++){
            //遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。
            if(s[fast] != ' '){
              //给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
              if(slow != 0) s[slow ++] = ' ';
              //补上该单词，遇到空格说明单词结束。
              while(fast < s.size() && s[fast] != ' ')  s[slow ++] = s[fast ++];
            }
          }
          //slow的大小即为去除多余空格后的大小。
          s.resize(slow);
        }

整体代码：

class Solution{
  public:
        /*翻转，区间写法：左闭右闭 []
        void reverse(string& s , int start , int end){
          for(int i = start , j = end ; i < j ; i ++ , j --)  swap(s[i] , s[j]);
        }
        我这里用库函数reverse
         */
  
        void removeExtraSpaces(string& s){
          int slow = 0;
          for(int fast = 0 ; fast < s.size() ; fast ++){
            //遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。
            if(s[fast] != ' '){
              //给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
              if(slow != 0) s[slow ++] = ' ';
              //补上该单词，遇到空格说明单词结束。
              while(fast < s.size() && s[fast] != ' ')  s[slow ++] = s[fast ++];
            }
          }
          //slow的大小即为去除多余空格后的大小。
          s.resize(slow);
        } 

       string reverseWords(string s) {
          //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
          removeExtraSpaces(s);
           reverse(s.begin() , s.end());//STL中reverse函数是左闭右开
          //removeExtraSpaces后保证第一个单词的开始下标一定是0。
          int start = 0;
          for(int i = 0 ; i <= s.size() ; i++){
            //到达空格或者串尾，说明一个单词结束。进行翻转。
            if(i == s.size() || s[i] == ' ') {
              //翻转，注意是左闭右闭 []的翻转。start ~ i - 1
             reverse(s.begin() + start , s.begin() + i);
              //更新下一个单词的开始下标start
              start = i + 1;
            }
          }
          return s;
       }
};

206.反转链表

题意描述：

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路：

只需改变next指针朝向，原地翻转即可，定义pre ， cur ， tmp 指针分别指向前，现在，下节点。

AC代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* tmp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            tmp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

另解：递归法

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解，可以看到双指针法中初始化cur = head``，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。
具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }

};

时间复杂度: O(n), 要递归处理链表的每个节点
空间复杂度: O(n), 递归调用了 n 层栈空间

我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。

具体代码如下（带详细注释）：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表，这一步仔细体会
        ListNode *last = reverseList(head->next);
      
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
};

19.删除链表的倒数第N个节点

题意描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]

思路：

定义双指针fast 、 slow ，先让fast走n + 1 步，然后fast 、 slow同时走，fast走到结尾时，slow的下一个元素恰好是待删除元素，此时令slow-> next = slow -> next -> next即可。

AC代码：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
      //while(n --)执行顺序说明：先判断n>0? 如果是则 -1
        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点,结合上面的图可以理解，这一步很重要
      
        while (fast != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; 
        
        // ListNode *tmp = slow->next;  C++释放内存的逻辑
        // slow->next = tmp->next;
        // delete tmp;
        
        return dummyHead->next;
    }
};

面试题 02.07. 链表相交

题意描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
[
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
[
1
2
3
4
5
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
[
1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

思路：

定义双指针curA 、curB, 目前curA指向链表A的头结点，curB指向链表B的头结点,计算AB链表长度差gap假如lenA > lenB（如果不是就swap（lenA，lenB）, swap(curA , curB)。让curA先走gap步，然后curA、curB同时走到末尾，过程中比较指针是否相等即可。

AC代码：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

M:142.环形链表II

题意描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶：你是否可以使用 O(1) 空间解决此题？

思路：

主要考察两知识点：
判断链表是否环
如果有环，如何找到这个环的入口
判断是否有环
定义快慢指针fast、slow， fast每次走两步，slow 每次走一步，若循环中相遇则有环。
环的入口
假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为z。如图所示：
那么相遇时： slow指针走过的节点数为: x + y，fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
1
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
取n为1，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

AC代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
      //这里的判断条件是fast和fast->next不为空
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇。上面推导n = 1的情况。
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

M:第15题. 三数之和

题意描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路：

滑动窗口思想，先排序数组，然后去重处理。一层for循环控制i遍历整个数组，然后定义双指针l、 r分别在nums[i] + nums[l] + nums[j] < 0和> 0时右滑/左滑。如果三数之和=0，则保存进res，然后去重处理处理，将r左移、l右移。
代码注意的几点：
结果返回的是[] 、[]的三元组形式，故定义res为二重数组vector<vector<int>>,然后在res.push_back的时候，参数是{vector<int>{nums[i] , nums[l] , nums[r]}}
else的逻辑，在三数之和 = 0时需将左右窗口分别移动，else push_back那里括号较多，应分行写。
res的return在for循环之后，写完要检查

AC代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      vector<vector<int>> res;
      sort(nums.begin() , nums.end());
      for(int i = 0 ; i < nums.size() ; i++){
        if(nums[i] > 0)  return res;

        if(i > 0 && nums[i] == nums[i - 1]) continue;

        int l = i + 1 , r = nums.size() - 1;
        while(r > l){
          if(nums[i] + nums[l] + nums[r] > 0) r--;
          else if(nums[i] + nums[l] + nums[r] <0) l++;
          else {
            res.push_back(vector<int>{nums[i] , nums[l] , nums[r]});

          while(r > l && nums[r] == nums[r - 1])  r--;
          while(r > l && nums[l] == nums[l + 1])  l ++;

          r --;
          l ++;
        			}
      	}   
    }
      return res;
    }
};

第18题. 四数之和

题意描述：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案。
示例 1：
1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

思路：

四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是再套一层for循环。
但是有一些细节需要注意，例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。
类似的二级剪枝：nums[i] + nums[j] > target && (nums[i] + nums[j] >= 0)
去重操作还是一样的。
三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2^)，四数之和的时间复杂度是O(n^3^) 。
那么一样的道理，五数之和、六数之和等等都采用这种解法。

AC代码：

class Solution {
public:
     vector<vector<int>> fourSum(vector<int>& nums, int target) {
      vector<vector<int>> res;
      sort(nums.begin() , nums.end());

      for(int i = 0 ; i < nums.size() ; i++){
         // 剪枝处理
        if(nums[i] > target && nums[i] >= 0)  break;// 这里使用break，统一通过最后的return返回
        // 对nums[i]去重
        if(i > 0 && nums[i] == nums[i - 1]) continue;

        for(int j = i + 1 ; j < nums.size() ; j++){
          // 二级剪枝处理
          if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0)  break;
          // 对nums[i]去重
          if(j > i + 1 && nums[j] == nums[j - 1])  continue;

          int l = j + 1 , r = nums.size() - 1;
          while(r > l){
            // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
          if((long)nums[i] + nums[j] + nums[l] + nums[r] > target) r--;
          else if((long)nums[i] + nums[j] + nums[l] + nums[r] < target) l++;
          else {
            res.push_back(vector<int>{nums[i] , nums[j] , nums[l] , nums[r]});
          // 对nums[left]和nums[right]去重
          while(r > l && nums[r] == nums[r - 1])  r--;
          while(r > l && nums[l] == nums[l + 1])  l ++;
          // 找到答案时，双指针同时收缩
          r --;
          l ++;
       }
    }
  }
}
      return res;
    
    }
};

代码随想录

#LEECODE

6.12-双指针

https://bing.7dragonpig.cn/posts/f9b0c129/

作者

七龙猪

发布于

2024年6月12日

许可协议

6.13-栈和队列上一篇

6.10/6.11-字符串下一篇