力扣整理版五：双指针法

主要是双指针法相关题型的总结。

------------------------------

(1) 27 移除元素

(2) 26 删除有序数组中的重复项

(3) 283 移动零

(4) 844 比较含退格的字符串

(5) 977 有序数组的平方

(6) 344 反转字符串

(7) 卡码网-替换数字

(8) 151 翻转字符串中的单词

(9) 206 反转链表

(10) 19 删除链表的倒数第N个结点

(11) 160 相交链表

(12) 环形链表2

(13) 15 三数之和

(14) 18 四数之和

------------------------------

一、27 移除元素

(1) 27 移除元素

题目描述：给你一个数组 nums 和一个值 val ，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

------------ python -----------

  1. class Solution:
  2.     def removeElement(self, nums: List[int], val: int) -> int:
  3.         slow=0
  4.         fast=len(nums)-1
  5.         while slow<=fast:
  6.             if nums[slow]==val:
  7.                 nums[slow]=nums[fast]
  8.                 fast-=1
  9.             else: slow+=1
  10.         return slow

注意是返回元素数量，所以是返回slow，如果是下标就是slow-1

时间复杂度O(n) 

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     int removeElement(vector<int>& nums, int val) {
  4.        int p=0;
  5.        int q=nums.size()-1;
  6.        while(p<=q){
  7.             if (nums[p]==val) nums[p]=nums[q--];
  8.             else p++;
  9.        }
  10.        return p;
  11.     }
  12. };

二、26 删除有序数组中的重复项

(2) 26 删除有序数组中的重复项

题目描述：给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

>>> 注意本题要求相对顺序保持一致。

------------ python -----------

  1. class Solution:
  2.     def removeDuplicates(self, nums: List[int]) -> int:
  3.         p=0
  4.         for q in range(1,len(nums)):
  5.             if nums[p]!=nums[q]:
  6.                 if q-p>1:
  7.                     nums[p+1]=nums[q]
  8.                 p+=1
  9.         return p+1

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         if(nums.empty()) return 0;
  5.         int left=0;
  6.         for(int needle=1;needlesize();needle++){
  7.             if(nums[needle]!=nums[left]){
  8.                 if(needle-left>1) nums[left+1]=nums[needle];
  9.                 left++;
  10.             }
  11.         }
  12.         return left+1;
  13.     }
  14. };

三、283 移动零

(3) 283 移动零

题目描述：给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

------------ python -----------

  1. class Solution:
  2.     def moveZeroes(self, nums: List[int]) -> None:
  3.         """
  4.         Do not return anything, modify nums in-place instead.
  5.         """
  6.         p=q=0
  7.         while q<len(nums):
  8.             if nums[q]!=0:
  9.                 nums[p],nums[q]=nums[q],nums[p]
  10.                 p+=1
  11.             q+=1

左指针处理好的序列的尾部，右指针待处理的头部。 每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     void moveZeroes(vector<int>& nums) {
  4.         int i=0;
  5.         for(int j=0;jsize();j++){
  6.             if(nums[j]!=0){
  7.                 int tem=nums[i];
  8.                 nums[i]=nums[j];
  9.                 nums[j]=tem;
  10.                 i++;
  11.             }
  12.         }
  13.     }
  14. };

四、844 比较含退格的字符串

(4) 844 比较含退格的字符串

题目描述：给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。

------------ python -----------

  1. class Solution:
  2.     def backspaceCompare(self, s: str, t: str) -> bool:
  3.         i,j=len(s)-1,len(t)-1
  4.         skips=skipt=0  #存放＃的数量
  5.  
  6.         while i>=0 or j>=0:
  7.             while i>=0:
  8.                 if s[i]=="#":
  9.                     skips+=1
  10.                     i-=1
  11.                 elif skips>0:
  12.                     skips-=1
  13.                     i-=1
  14.                 else:
  15.                     break
  16.             while j>=0:
  17.                 if t[j]=="#":
  18.                     skipt+=1
  19.                     j-=1
  20.                 elif skipt>0:
  21.                     skipt-=1
  22.                     j-=1
  23.                 else:
  24.                     break
  25.             if i>=0 and j>=0:
  26.                 if s[i]!=t[j]:
  27.                     return False
  28.             elif i>=0 or j>=0:
  29.                 return False
  30.             i-=1
  31.             j-=1
  32.         return True

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     bool backspaceCompare(string s, string t) {
  4.         int sn=s.size()-1;
  5.         int tn=t.size()-1;
  6.         int sc=0;
  7.         int tc=0;
  8.         while(sn>=0 || tn>=0){
  9.             while(sn>=0){
  10.                 if(s[sn]=='#') sn--, sc++;
  11.                 else if(sc>0)  sn--, sc--;
  12.                 else break;
  13.             }
  14.             while(tn>=0){
  15.                 if(t[tn]=='#') tn--, tc++;
  16.                 else if(tc>0)  tn--, tc--;
  17.                 else break;
  18.             }
  19.             if(sn>=0 && tn>=0) {
  20.                 if(s[sn]!=t[tn]) return false;
  21.             }
  22.             else if(sn>=0 || tn>=0) return false;
  23.             sn--, tn--;
  24.         } 
  25.         return true;
  26.     }
  27. };

五、977 有序数组的平方

(5) 977 有序数组的平方

题目描述：给你一个按 非递减顺序 排序的整数数组 nums ，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

------------ python -----------

  1. class Solution:
  2.     def sortedSquares(self, nums: List[int]) -> List[int]:
  3.         n = len(nums)
  4.         ans = [0] * n
  5.         
  6.         i, j, pos = 0, n - 1, n - 1
  7.         while i <= j:
  8.             if nums[i] * nums[i] > nums[j] * nums[j]:
  9.                 ans[pos] = nums[i] * nums[i]
  10.                 i += 1
  11.             else:
  12.                 ans[pos] = nums[j] * nums[j]
  13.                 j -= 1
  14.             pos -= 1
  15.         
  16.         return ans

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     vector<int> sortedSquares(vector<int>& nums) {
  4.         int i=0,j=nums.size()-1;
  5.         vector<int> ans(nums.size(),0);
  6.         for(int n=nums.size()-1;n>=0;n--){
  7.             if(abs(nums[i])<=abs(nums[j])){
  8.                 ans[n]=nums[j]*nums[j];
  9.                 j--;
  10.             }
  11.             else{
  12.                 ans[n]=nums[i]*nums[i];
  13.                 i++;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. };

六、344 反转字符串

(6) 344 反转字符串

题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

------------ python -----------

  1. class Solution:
  2.     def reverseString(self, s: List[str]) -> None:
  3.         """
  4.         Do not return anything, modify s in-place instead.
  5.         """
  6.         left=0
  7.         right=len(s)-1
  8.         # while left!=right:  这么写在长度为偶数时会导致越界
  9.         while left
  10.             # s[left],s[right]=s[right],s[left]
  11.             tem=s[left]
  12.             s[left]=s[right]
  13.             s[right]=tem
  14.             left+=1
  15.             right-=1
  16.         return s

------------ c++ -----------

  1. class Solution {
  2. public:
  3.     void reverseString(vector<char>& s) {
  4.         int left=0;
  5.         int right=s.size()-1;
  6.         while (left
  7.             // swap(s[left],s[right]);
  8.             char ch=s[left];
  9.             s[left]=s[right];
  10.             s[right]=ch;
  11.             left++;
  12.             right--;
  13.         }
  14.     }
  15. };

七、替换数字

(7) 卡码网-替换数字

题目描述：给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

------------ python -----------

  1. class Solution:
  2.     def change(self, s):
  3.         lst = list(s) # Python里面的string也是不可改的，所以也是需要额外空间的。空间复杂度：O(n)。
  4.         for i in range(len(lst)):
  5.             if lst[i].isdigit():
  6.                 lst[i] = "number"
  7.         return ''.join(lst)

------------ c++ -----------

  1. #include 
  2. using namespace std;
  3. int main() {
  4.     string s;
  5.     while (cin >> s) {
  6.         int sOldIndex = s.size() - 1;
  7.         int count = 0; // 统计数字的个数
  8.         for (int i = 0; i < s.size(); i++) {
  9.             if (s[i] >= '0' && s[i] <= '9') {
  10.                 count++;
  11.             }
  12.         }
  13.         // 扩充字符串s的大小，也就是将每个数字替换成"number"之后的大小
  14.         s.resize(s.size() + count * 5);
  15.         int sNewIndex = s.size() - 1;
  16.         // 从后往前将数字替换为"number"
  17.         while (sOldIndex >= 0) {
  18.             if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
  19.                 s[sNewIndex--] = 'r';
  20.                 s[sNewIndex--] = 'e';
  21.                 s[sNewIndex--] = 'b';
  22.                 s[sNewIndex--] = 'm';
  23.                 s[sNewIndex--] = 'u';
  24.                 s[sNewIndex--] = 'n';
  25.             } else {
  26.                 s[sNewIndex--] = s[sOldIndex];
  27.             }
  28.             sOldIndex--;
  29.         }
  30.         cout << s << endl;       
  31.     }
  32. }

八、151 翻转字符串里的单词

(8) 151 翻转字符串中的单词

题目描述：给你一个字符串 s ，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

------------ python -----------

  1. class Solution:
  2.     def reverseWords(self, s: str) -> str:
  3.         # 删除前后空白
  4.         s = s.strip()
  5.         # 反转整个字符串
  6.         s = s[::-1]
  7.         # 将字符串拆分为单词，并反转每个单词
  8.         s = ' '.join(word[::-1] for word in s.split())
  9.         return s
  1. class Solution:
  2.     def reverseWords(self, s: str) -> str:
  3.         # 将字符串拆分为单词，即转换成列表类型
  4.         words = s.split()
  5.  
  6.         # 反转单词
  7.         left, right = 0, len(words) - 1
  8.         while left < right:
  9.             words[left], words[right] = words[right], words[left]
  10.             left += 1
  11.             right -= 1
  12.  
  13.         # 将列表转换成字符串
  14.         return " ".join(words)

 ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
  4.         for (int i = start, j = end; i < j; i++, j--) {
  5.             swap(s[i], s[j]);
  6.         }
  7.     }
  8.  
  9.     void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
  10.         int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
  11.         for (int i = 0; i < s.size(); ++i) { //
  12.             if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
  13.                 if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
  14.                 while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
  15.                     s[slow++] = s[i++];
  16.                 }
  17.             }
  18.         }
  19.         s.resize(slow); //slow的大小即为去除多余空格后的大小。
  20.     }
  21.  
  22.     string reverseWords(string s) {
  23.         removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
  24.         reverse(s, 0, s.size() - 1);
  25.         int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
  26.         for (int i = 0; i <= s.size(); ++i) {
  27.             if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
  28.                 reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
  29.                 start = i + 1; //更新下一个单词的开始下标start
  30.             }
  31.         }
  32.         return s;
  33.     }
  34. };

九、206 反转链表

(9) 206 反转链表

题目描述：反转一个链表。

------------ python -----------

  1. class Solution:
  2.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  3.         if not head or not head.next:return head
  4.         pre=None
  5.         while head:
  6.             nxt=head.next
  7.             head.next=pre
  8.             pre=head
  9.             head=nxt
  10.         return pre
  11. 》》》
  12. pre=None
  13. pre.next=head
  14. ————————————————
  15. AttributeError: 'NoneType' object has no attribute 'next'
  1. class Solution:
  2.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  3.         if not head or not head.next:
  4.             return head
  5.         newhead=self.reverseList(head.next)
  6.         head.next.next=head
  7.         head.next=None
  8.         return newhead

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* pre=nullptr;
  5.         while(head){
  6.                 ListNode* nxt=head->next;
  7.                 head->next=pre;
  8.                 pre=head;
  9.                 head=nxt;
  10.         }
  11.         return pre;
  12.     }
  13. };
  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         if(head==nullptr || head->next==nullptr) return head;
  5.         ListNode* newhead=reverseList(head->next);
  6.         head->next->next=head;
  7.         head->next=nullptr;
  8.         return newhead;
  9.     }
  10. };

十、19 删除链表的倒数第N个结点

(10) 19 删除链表的倒数第N个结点

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

------------ python -----------

  1. class Solution:
  2.     def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
  3.         pre=ListNode(0)
  4.         pre.next=head
  5.         fast=pre
  6.         slow=pre
  7.         while fast and n: #while n也可以
  8.             fast=fast.next
  9.             n-=1
  10.         fast=fast.next
  11.         while fast:
  12.             fast=fast.next
  13.             slow=slow.next
  14.         slow.next=slow.next.next
  15.         return pre.next

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  4.         ListNode* dummyHead = new ListNode(0);
  5.         dummyHead->next = head;
  6.         //ListNode* slow=pre,fast=pre;
  7.         //这样写会报错，c++无法自动推断fast类型（变量声明无法自动推导）
  8.         ListNode* slow = dummyHead;
  9.         ListNode* fast = dummyHead;
  10.         while(n-- && fast != NULL) {
  11.             fast = fast->next;
  12.         }
  13.         fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点
  14.         while (fast != NULL) {
  15.             fast = fast->next;
  16.             slow = slow->next;
  17.         }
  18.         slow->next = slow->next->next; 
  19.         
  20.         // ListNode *tmp = slow->next;  C++释放内存的逻辑
  21.         // slow->next = tmp->next;
  22.         // delete tmp;
  23.         
  24.         return dummyHead->next;
  25.     }
  26. };

十一、160 链表相交

(11) 160 相交链表

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

------------ python -----------

  1. class Solution:
  2.     def getIntersectionNode(self, A: ListNode, B: ListNode) -> Optional[ListNode]:
  3.         if not A or not B: return None
  4.         headA=A 
  5.         headB=B 
  6.         while A!=B:
  7.             if A: A=A.next
  8.             else: A=headB
  9.             if B: B=B.next
  10.             else: B=headA
  11.         return A

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  4.         if(!headA || !headB) return nullptr;
  5.         ListNode *p1=headA;
  6.         ListNode *p2=headB;
  7.         while(p1!=p2){
  8.             p1=p1!=nullptr?p1->next:headB;
  9.             p2=p2!=nullptr?p2->next:headA;
  10.         }
  11.         return p1;
  12.     }
  13. };

十二、142 环形链表2

(12) 142 环形链表2

题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

------------ python -----------

  1. class Solution:
  2.     def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
  3.         f=head
  4.         s=head
  5.         while f and f.next:
  6.             s=s.next
  7.             f=f.next.next
  8.             if s==f:
  9.                 index1=f
  10.                 index2=head
  11.                 while index1!=index2:
  12.                     index1=index1.next
  13.                     index2=index2.next
  14.                 return index1
  15.         return None

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     ListNode *detectCycle(ListNode *head) {
  4.         ListNode* fast = head;
  5.         ListNode* slow = head;
  6.         #需要从同一点开始，不然会有偏差
  7.         while(fast != NULL && fast->next != NULL) {
  8.             slow = slow->next;
  9.             fast = fast->next->next;
  10.             // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
  11.             if (slow == fast) {
  12.                 ListNode* index1 = fast;
  13.                 ListNode* index2 = head;
  14.                 while (index1 != index2) {
  15.                     index1 = index1->next;
  16.                     index2 = index2->next;
  17.                 }
  18.                 return index2; // 返回环的入口
  19.             }
  20.         }
  21.         return nullptr;
  22.     }
  23. };

十三、15 三数之和

(13) 15 三数之和

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

------------ python -----------

  1. class Solution:
  2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
  3.         result = []
  4.         nums.sort()
  5.         
  6.         for i in range(len(nums)):
  7.             # 如果第一个元素已经大于0，不需要进一步检查
  8.             if nums[i] > 0:
  9.                 return result
  10.             
  11.             # 跳过相同的元素以避免重复
  12.             if i > 0 and nums[i] == nums[i - 1]:
  13.                 continue
  14.                 
  15.             left = i + 1
  16.             right = len(nums) - 1
  17.             
  18.             while right > left:
  19.                 sum_ = nums[i] + nums[left] + nums[right]
  20.                 
  21.                 if sum_ < 0:
  22.                     left += 1
  23.                 elif sum_ > 0:
  24.                     right -= 1
  25.                 else:
  26.                     result.append([nums[i], nums[left], nums[right]])
  27.                     
  28.                     # 跳过相同的元素以避免重复
  29.                     while right > left and nums[right] == nums[right - 1]:
  30.                         right -= 1
  31.                     while right > left and nums[left] == nums[left + 1]:
  32.                         left += 1
  33.                         
  34.                     right -= 1
  35.                     left += 1
  36.                     
  37.         return result

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     vectorint>> threeSum(vector<int>& nums) {
  4.         vectorint>> result;
  5.         sort(nums.begin(), nums.end());
  6.         // 找出a + b + c = 0
  7.         // a = nums[i], b = nums[left], c = nums[right]
  8.         for (int i = 0; i < nums.size(); i++) {
  9.             // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
  10.             if (nums[i] > 0) {
  11.                 return result;
  12.             }
  13.             // 错误去重a方法，将会漏掉-1,-1,2 这种情况
  14.             /*
  15.             if (nums[i] == nums[i + 1]) {
  16.                 continue;
  17.             }
  18.             */
  19.             // 正确去重a方法
  20.             if (i > 0 && nums[i] == nums[i - 1]) {
  21.                 continue;
  22.             }
  23.             int left = i + 1;
  24.             int right = nums.size() - 1;
  25.             while (right > left) {
  26.                 // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
  27.                 /*
  28.                 while (right > left && nums[right] == nums[right - 1]) right--;
  29.                 while (right > left && nums[left] == nums[left + 1]) left++;
  30.                 */
  31.                 if (nums[i] + nums[left] + nums[right] > 0) right--;
  32.                 else if (nums[i] + nums[left] + nums[right] < 0) left++;
  33.                 else {
  34.                     result.push_back(vector<int>{nums[i], nums[left], nums[right]});
  35.                     // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
  36.                     while (right > left && nums[right] == nums[right - 1]) right--;
  37.                     while (right > left && nums[left] == nums[left + 1]) left++;
  38.  
  39.                     // 找到答案时，双指针同时收缩
  40.                     right--;
  41.                     left++;
  42.                 }
  43.             }
  44.  
  45.         }
  46.         return result;
  47.     }
  48. };

十四、18 四数之和

(14) 18 四数之和

题目描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

------------ python -----------

  1. class Solution:
  2.     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
  3.         nums.sort()
  4.         n=len(nums)
  5.         result=[]
  6.  
  7.         for i in range(n):
  8.             if nums[i]>target and nums[i]>=0: #剪枝
  9.                 break
  10.             if i>0 and nums[i]==nums[i-1]: #去重
  11.                 continue
  12.             for j in range(i+1,n):
  13.                 if nums[i]+nums[j]>target and nums[i]+nums[j]>=0: #剪枝
  14.                     break
  15.                 if j>i+1 and nums[j]==nums[j-1]: #去重
  16.                     continue
  17.                 left,right=j+1,n-1 
  18.                 while left
  19.                     s=nums[i]+nums[j]+nums[left]+nums[right]
  20.                     if s==target:
  21.                         result.append([nums[i], nums[j], nums[left], nums[right]])
  22.                         while leftand nums[left]==nums[left+1]:
  23.                             left+=1
  24.                         while left < right and nums[right] == nums[right-1]:
  25.                             right -= 1
  26.                         left += 1
  27.                         right -= 1
  28.                     elif s
  29.                         left+=1
  30.                     else:
  31.                         right-=1
  32.         return result

  ------------ c++ -----------

  1. class Solution {
  2. public:
  3.     vectorint>> fourSum(vector<int>& nums, int target) {
  4.         vectorint>> result;
  5.         sort(nums.begin(), nums.end());
  6.         for (int k = 0; k < nums.size(); k++) {
  7.             // 剪枝处理
  8.             if (nums[k] > target && nums[k] >= 0) {
  9.             	break; // 这里使用break，统一通过最后的return返回
  10.             }
  11.             // 对nums[k]去重
  12.             if (k > 0 && nums[k] == nums[k - 1]) {
  13.                 continue;
  14.             }
  15.             for (int i = k + 1; i < nums.size(); i++) {
  16.                 // 2级剪枝处理
  17.                 if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
  18.                     break;
  19.                 }
  20.  
  21.                 // 对nums[i]去重
  22.                 if (i > k + 1 && nums[i] == nums[i - 1]) {
  23.                     continue;
  24.                 }
  25.                 int left = i + 1;
  26.                 int right = nums.size() - 1;
  27.                 while (right > left) {
  28.                     // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
  29.                     if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
  30.                         right--;
  31.                     // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
  32.                     } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
  33.                         left++;
  34.                     } else {
  35.                         result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
  36.                         // 对nums[left]和nums[right]去重
  37.                         while (right > left && nums[right] == nums[right - 1]) right--;
  38.                         while (right > left && nums[left] == nums[left + 1]) left++;
  39.  
  40.                         // 找到答案时，双指针同时收缩
  41.                         right--;
  42.                         left++;
  43.                     }
  44.                 }
  45.  
  46.             }
  47.         }
  48.         return result;
  49.     }
  50. };

注：本文转载自blog.csdn.net的cherry_rainyyy的文章"https://blog.csdn.net/qq_51398395/article/details/143729920"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！