這里是阿川的博客，祝您變得更強(qiáng)

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

---

寫在開頭

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

---

---

1. 題目介紹

難度：中
題目練習(xí)：四數(shù)之和
題目信息：給你一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組 nums ，和一個(gè)目標(biāo)值 target 。請(qǐng)你找出并返回滿足下述全部條件且不重復(fù)的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意順序 返回答案 。
舉個(gè)例子： 具體如圖1所示

圖1 舉個(gè)例子

---

2. 題目拆解

本質(zhì)上：觀察規(guī)律，雙指針遍歷判斷
特點(diǎn)是：在組合搭配中有一定規(guī)律
解決方法：雙指針?biāo)惴?#xff0c;如圖2所示

圖2 雙指針

---

3. 具體詳情

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

---

4. 具體代碼

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, long long target){// 進(jìn)行排序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];// 雙指針?biāo)惴ň唧w實(shí)現(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. 夾帶私貨

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

---

好的，到此為止啦，祝您變得更強(qiáng)

道阻且長 行則將至
個(gè)人主頁：在線OJ的阿川大佬的支持和鼓勵(lì)，將是我成長路上最大的動(dòng)力