首页 > 代码库 > 【LeetCode】18. 4Sum 解题小结
【LeetCode】18. 4Sum 解题小结
题目：
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]
这个题目是上一道题目的延伸，再嵌套一次循环确实可以解决这个问题，不过多了两个判断的情况，若最小和大于target，那么停止循环。
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; int n = nums.size(); if (nums.size()<4) return res; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() - 3; i++){ if (i > 0 && nums[i] == nums[i-1]) continue; if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)break; if (nums[i]+nums[n-3]+nums[n-2]+nums[n-1] < target)continue; for (int j = i+1; j < nums.size() - 2; j++){ if (j > i+1 && nums[j] == nums[j-1])continue; if (nums[i]+nums[j]+nums[j+1]+nums[j+2] > target)break; if (nums[i]+nums[j]+nums[n-2]+nums[n-1] < target)continue; int left = j + 1; int right = n - 1; while(left < right){ if (nums[i]+nums[j]+nums[left]+nums[right] < target)left++; else if (nums[i]+nums[j]+nums[left]+nums[right] > target)right--; else{ res.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]}); do{left++;}while(left<right && nums[left]==nums[left-1]); do{right--;}while(left<right && nums[right]==nums[right+1]); } } } } return res; }};
那么问题来了，如果扩展的K个数的和呢？有没有更好的一般性的解决方案呢？在LeetCode上该题的Discussion上有人贴出的代码如下，可以大家参考参考读读：
void KSum(int k, vector<int>& nums, int l, int r, int target, vector<vector<int>>& retVal, vector<int>& cur, int ci ) { int i, mn, mx; int km1 = k - 1; if ( r-l+1 < k ) return; while ( l < r ) { mn = nums[l]; mx = nums[r]; // If K minus 1 largest + min < target, move to larger if ( ( mn + km1*mx ) < target ) l++; // If K minus 1 smaller + max > target, move to smaller else if ( ( km1*mn + mx ) > target ) r--; // If K * min > target, stop looking else if ( k*mn > target ) break; // If K * min == target, reached the threshold, check then stop looking else if ( k*mn == target ) { if ( ( l + km1 <= r ) && ( mn == ( nums[l+km1] ) ) ) { for ( i = 0; i < k; i++ ) cur[ci+i] = mn; retVal.push_back( cur ); } break; } // If K * max < target, stop looking else if ( k*mx < target ) break; // If K * max == target, reached the threshold, check then stop looking else if ( k*mx == target ) { if ( ( l <= r - km1 ) && ( mx == ( nums[r-km1] ) ) ) { for ( i = 0; i < k; i++ ) cur[ci+i] = mx; retVal.push_back( cur ); } break; } // If K == 2, we found a match! else if ( k == 2 ) { cur[ci] = mn; cur[ci+1] = mx; retVal.push_back( cur ); l++; while ( ( l < r ) && ( nums[l] == mn ) ) l++; r--; while ( ( l < r ) && ( nums[r] == mx ) ) r--; } // Otherwise, convert the problem to a K-1 problem else { cur[ci] = mn; KSum( km1, nums, ++l, r, target - mn, retVal, cur, ci+1 ); while ( ( l < r ) && ( nums[l] == nums[l-1] ) ) l++; } } }
【LeetCode】18. 4Sum 解题小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。