四數之和，和三數之和是一個思路，都是使用雙指針法, 基本解法就是在三數之和 的基礎上再套一層for循環。

但是要注意，不要判斷nums[ii] > target 就返回了，三數之和 可以通過 nums[i] > 0 就返回了，因為 0 已經是確定的數了，四數之和這道題目 target是任意值。

比如這個例子就不能通過
[1,-2,-5,-4,-3,3,3,5]
-11

三數之和的雙指針解法是一層for循環num[i]為確定值，然后循環內有left和right下表作為雙指針，找到nums[ii] + nums[left] + nums[right] == 0。

四數之和的雙指針解法是兩層for循環nums[ii] + nums[jj]為確定值，依然是循環內有left和right下表作為雙指針，找出nums[ii] + nums[jj] + nums[left] + nums[right] == target的情況，三數之和的時間復雜度是O(n^{2)，四數之和的時間復雜度是O(n}3) 。

那么一樣的道理，五數之和、六數之和等等都采用這種解法。

對于三數之和雙指針法就是將原本暴力O(n^{3)的解法，降為O(n}2)的解法，四數之和的雙指針解法就是將原本暴力O(n^{4)的解法，降為O(n}3)的解法。

之前的一道哈希表的經典題目：四數相加II，相對于本題簡單很多，因為本題是要求在一個集合中找出四個數相加等于target，同時四元組不能重復。

而四數相加II是四個獨立的數組，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮有重復的四個元素相加等于0的情況，所以相對于本題還是簡單了不少！

雙指針法

class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin(),nums.end());for(int ii=0;ii<nums.size();ii++){if(ii>0&&nums[ii]==nums[ii-1]) continue;for(int jj=ii+1;jj<nums.size();jj++){if(jj>ii+1&&nums[jj]==nums[jj-1]) continue;int left=jj+1,right=nums.size()-1;while(left<right){if(nums[ii]+nums[jj]+nums[left]+nums[right]<target) left++;else if(nums[ii]+nums[jj]+nums[left]+nums[right]>target) right--;else {res.push_back({nums[ii],nums[jj],nums[left],nums[right]});while(left<right&&nums[right]==nums[right-1]) right--;while(left<right&&nums[left]==nums[left+1]) left++;left++;right--;}}}}return res; } };

總結

以上是生活随笔為你收集整理的四数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。