前言
哈希篇，繼續。
記錄 二十【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：
輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
輸入：nums = [2,2,2,2,2], target = 8
輸出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
二、嘗試實現
學過“三數之和”，同法炮制可以求解4數之和。但是同樣有問題需要注意，先上代碼，再說細節點：
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());//排序vector<vector<int>> result;if((nums[nums.size()-1] < 0 && target >= 0) || (nums[0] > 0 && target <= 0)){return result;}for(int a = 0;a < nums.size();a++){if(a > 0 && nums[a] == nums[a-1]){ //a去重continue;}for(int b = a+1;b < nums.size();b++){if((b-1 > a) && nums[b] == nums[b-1]){///b-1>a。continue;}int c = b+1;int d = nums.size()-1;while(c < d){if(nums[a] + nums[b] > target - nums[c] - nums[d]){d--;}else if(nums[a] + nums[b] < target- nums[c]- nums[d]){c++;}else{result.push_back({nums[a],nums[b],nums[c],nums[d]});while(c < d && nums[d] == nums[d-1]){d--;}while(c < d && nums[c] == nums[c+1]){c++;}c++;d--;}}}}return result;}
};
細節及區別：
-
a,b,c,d分別去重；用c、d作為活動區間，所以c,d去重兩個while，注意c<d即可；a去重，保證下標不違法，逐步后移。
- 重點是b去重，第二層循環，b=a+1，從a+1開始，所以去重應該（b-1 > a），否則nums[b]和nums[a]比較，錯誤。另外因為先b++再去重，所以nums[b]和nums[b-1]比較。
-
直接返回部分：
if((nums[nums.size()-1] < 0 && target >= 0) || (nums[0] > 0 && target <= 0)){return result;}- target不再是0，nums元素有正有負（注意提示）。所以能夠直接返回的條件是：
- nums全為負，target >=0，肯定空；
- nums全為正，target <=0，肯定空；
-
提示：-109 <= nums[i] <= 109，說明可能(nums[a] + nums[b] +nums[c] + nums[d])超出“int”類型范圍，導致運行錯誤。
- 怎么控制求和不超過int類型最大值？
- 把nums[c] + nums[d]移到等式的右邊，3個109相加超過int，2個109相加可以不超過int范圍。
代碼隨想錄學習
學習內容
思路：同思路。
代碼實現區別：
-
去重——操作一樣。回顧細節部分第一點；
-
剪枝：有所區別。回顧細節部分第二點；
- 參考給出的剪枝操作，分別在第一層a所在循環和第二層b所在循環。
- 第一層循環剪枝：(nums[a] > target && nums[a] > 0 )。解釋原因：nums[a]>0，后面的肯定也是大于0（排過序），加正數會越加越大。所以可以break;
- 第二層循環剪枝：(nums[a] +nums[b]> target && nums[a] +nums[b] >= 0 )，把nums[a] +nums[b]看作一個整體。為什么呢？
- target>=0時候肯定沒有問題；
- 當target < 0，nums[a] +nums[b] >= 0，那么nums[b] 一定>= 0，保證nums[b]后面都是正數，往后會越加越大，所以可以break;
- 如果只是nums[b] >= 0，可以嗎？可以。因為nums[b]往后都是正數，加正數會越加越大。在nums[a] +nums[b]> target的基礎上。
- 所以第一個條件得是nums[a] +nums[b]> target 。
-
超出范圍怎么處理？回顧細節部分第三點；
- 直接轉換成long類型。
總結
和“三數之和”思路一致，但同樣有細節需要主要：3點。
（歡迎指正，轉載表明出處）
