給定一個包含?n?個整數的數組?nums?和一個目標值?target，判斷?nums?中是否存在四個元素?a，b，c?和?d?，使得?a?+?b?+?c?+?d?的值與?target?相等？找出所有滿足條件且不重復的四元組。

注意：

答案中不可以包含重復的四元組。

示例：

給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。滿足要求的四元組集合為：
[[-1,  0, 0, 1],[-2, -1, 1, 2],[-2,  0, 0, 2]
]

思路：

（1）我們可以用遞歸的方法。將四數之和轉換為三數之和，然后轉換為兩數之和。先將數組中的數排序，然后調用函數處理。這樣就需要一個函數，個數和目標值都通過傳參的方式獲取。還需要一個開始的位置，也通過參數傳遞進去。如果剛好轉換的是兩數之和，那么我們可以利用前面已經解決過的兩數之和的方法來處理，用unordered_set來處理重復的元素，判斷有沒有被訪問過，以免一個元素重復使用。如果不是兩個數的和，那么我們將這個數先記下來，直到是判斷兩個數的和?？傊褪窍裙潭▋蓚€數，然后用two-sum的方法來找另外兩個數。

　　vector<vector<int>> k_Sum(vector<int> &nums, int begPos, int count, int target){if (nums.empty())return vector<vector<int>>();/*所輸入序列為已排序*/int len = nums.size();unordered_set<int> visited;vector<vector<int>> ret;vector<int> tmp;/*2-sum 處理*/if (2 == count){int i = begPos, j = len - 1;while (i < j){int sum = nums[i] + nums[j];if (sum == target && visited.find(nums[i]) == visited.end()){tmp.clear();tmp.push_back(nums[i]);tmp.push_back(nums[j]);ret.push_back(tmp);/*加入已訪問set*/visited.insert(nums[i]);visited.insert(nums[j]);++i;--j;}//ifelse if (sum < target)++i;else--j;}//while}//ifelse{for (int i = begPos; i < len; ++i){if (visited.find(nums[i]) == visited.end()){visited.insert(nums[i]);/*得到k-1 sum的序列*/vector<vector<int>> subRet = k_Sum(nums, i+1, count - 1, target-nums[i]);if (!subRet.empty()){int sz = subRet.size();for (int j = 0; j < sz; ++j){subRet[j].insert(subRet[j].begin(), nums[i]);}//for
                        ret.insert(ret.end(), subRet.begin(), subRet.end());}//if}//if}//for}//else/*返回結果集*/return ret;}/*4-sum算法，遞歸實現，TLE*/vector<vector<int>> fourSum(vector<int>& nums, int target) {if (nums.empty())return vector<vector<int>>();sort(nums.begin(), nums.end());return k_Sum(nums, 0, 4, target);}

（2）思路是一樣的，但是沒有用遞歸的方式

    vector<vector<int>> fourSum(vector<int>& nums, int target){if (nums.empty() || nums.size() < 4)return vector<vector<int>>();sort(nums.begin(), nums.end());int len = nums.size();set<vector<int>> tmpRet;vector<vector<int>> res;for (int i = 0; i < len; ++i){for (int j = i + 1; j < len; ++j){int beg = j + 1, end = len - 1;while (beg < end){int sum = nums[i] + nums[j] + nums[beg] + nums[end];if (sum == target){vector<int> tmp;tmp.push_back( nums[i]);tmp.push_back( nums[j]);tmp.push_back( nums[beg]);tmp.push_back( nums[end]);tmpRet.insert(tmp);++beg;--end;}else if (sum < target){++beg;}else--end;}//while}//for}//forauto iter = tmpRet.begin();while (iter != tmpRet.end()){res.push_back(*iter);++iter;}//whilereturn res;}

?

轉載于:https://www.cnblogs.com/mini-coconut/p/9193206.html

總結

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

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