這里是阿川的博客，祝您變得更強

? 個人主頁：在線OJ的阿川
💖文章專欄：OJ刷題入門到進階
🌏代碼倉庫：

---

寫在開頭

現(xiàn)在您看到的是我的結(jié)論或想法，但在這背后凝結(jié)了大量的思考、經(jīng)驗和討論

---

---

1. 題目介紹

難度：中
題目練習：四數(shù)之和
題目信息：給你一個由 n 個整數(shù)組成的數(shù)組 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. 題目拆解

本質(zhì)上：觀察規(guī)律，雙指針遍歷判斷
特點是：在組合搭配中有一定規(guī)律
解決方法：雙指針算法，如圖2所示

圖2 雙指針

---

3. 具體詳情

1. 先進行排序
2. 依次固定一個數(shù)并確保固定時，若是重復固定值時跳過
3. 在固定數(shù)后面的區(qū)間內(nèi)利用"三數(shù)之和"找到三個數(shù)，然后再固定一個數(shù)，在固定的這個數(shù)后面的區(qū)間內(nèi)，利用"雙指針"找到兩個數(shù)，使這兩個數(shù)的和等于目標值減去兩個固定值并遍歷完整個數(shù)組，并確保當雙指針和固定值是重復值時跳過
4. 最后返回數(shù)組

---

4. 具體代碼

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, long long target){// 進行排序sort(nums.begin(), nums.end());vector<vector<int>> cur;int n = nums.size();// 第1層固定值for(int i = 0; i < n; ){// 第2層固定值for(int j = i + 1; j < n; ){int left = j + 1, right = n - 1;long long aim = target - nums[i] - nums[j];// 雙指針算法具體實現(xiàn)while(left < right){int sum = nums[left] + nums[right];// 三種情況if(sum > aim) right--;else if(sum < aim) left++;else{cur.push_back({nums[i], nums[j], nums[left++], nums[right--]});// 去重while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}j++;// 第2層固定值去重while(j < n && nums[j] == nums[j - 1]) j++;}i++;// 第1層固定值去重while(i < n && nums[i] == nums[i - 1]) i++;}return cur;}
};

5. 夾帶私貨

若你能看到看到這篇文章且能看到這，則說明你我有緣，留個關注吧，后面還會接著計算機408、底層原理、開源項目、以及數(shù)據(jù)、后端研發(fā)相關、實習、筆試/面試、秋招/春招、各種競賽相關、簡歷相關、考研、學術相關……，祝你我變得更強

---

好的，到此為止啦，祝您變得更強

道阻且長 行則將至
個人主頁：在線OJ的阿川大佬的支持和鼓勵，將是我成長路上最大的動力