題目：
原以為很簡單的一題，結果想了超久之後也只拿到了一個效率奇差的解。
一開始想了一個 O(N^3) 的解法，簡單算了下 200^3 == 8000000。覺的怪怪的，這應該已經 TLE 了吧！？所以一直以為有 O(N^2) 的解。卡在這個念頭上卡了好久。
但其實組合數 200 取 3 也就 2000000 上下而已，應該還不到 TLE 的程度。。。白白浪費了好多的時間。
另外一個需要克服的難題就是，要如何讓得出的解不重複呢？我也在這個問題上打轉了好久。
醜解法：
runtime : 1556 ms
memory : 409.9 MB ( 爛透了 )
先將 nums 進行排序。為了避免重複，前兩數的選擇用 two pointers ， 遇到相同的數就再往下跳一格。後兩數的選擇用 two sums 去解 ( hash map )。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0;i < nums.size();) {
target -= nums[i];
for(int j = nums.size() - 1;j > i;) {
target -= nums[j];
unordered_map<int, int> um;
for(int q = i + 1;q < j;q++) {
um[nums[q]]++;
}
for(int q = i + 1;q < j;) {
if((target - nums[q] >= nums[q]) && um.find(target - nums[q]) != um.end()) {
if(target - nums[q] == nums[q]) {
if(um[nums[q]] >= 2) {
ans.push_back({nums[i], nums[j], nums[q], target - nums[q]});
}
} else {
ans.push_back({nums[i], nums[j], nums[q], target - nums[q]});
}
}
q++;
while(q < j && nums[q] == nums[q - 1]) {
q++;
}
}
target += nums[j];
j--;
while(j > i && nums[j] == nums[j + 1]) {
j--;
}
}
target += nums[i];
i++;
while(i < nums.size() && nums[i] == nums[i - 1]) {
i++;
}
}
return ans;
}
}:因為 hash map 的解法需要對重複的解多做處理，所以才跑出了這一段 code。
if((target - nums[q] >= nums[q]) && um.find(target - nums[q]) != um.end()) {
if(target - nums[q] == nums[q]) {
if(um[nums[q]] >= 2) {
ans.push_back({nums[i], nums[j], nums[q], target - nums[q]});
}
} else {
ans.push_back({nums[i], nums[j], nums[q], target - nums[q]});
}
}現在想想就覺得好笨，既然想的到前兩數為了避免重複，需要用 two pointers 的解法，為什麼後兩數不也用 two pointers 呢...
稍微不醜的解法：
runtime : 72 ms
memory : 13.3MB ( 好像沒這麼爛了 )
這個解法一樣開頭先排序好，接下來就是巢狀的遍尋，遍尋到最後剩下 two sum 的時候，就可以用 two pointers 的解法來得解。但因為我前兩個數的選取沒有處理好，所以最後還需要排除掉重複的解。有多留心的話，第二次的排序是完全不必要的。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
if(nums.size() < 4){
return ans;
}
sort(nums.begin(), nums.end());
for(int i = 0;i < nums.size()-3;i++){
for(int j = i+1;j < nums.size()-2;j++){
int left = j + 1;
int right = nums.size()-1;
while(left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if(sum == target){
ans.push_back({nums[i], nums[j], nums[left], nums[right]});
left++;
right--;
} else if(sum < target){
left++;
} else {
right--;
}
}
}
}
if(ans.size() == 0){
return ans;
}
sort(ans.begin(), ans.end());
vector<vector<int>> newans;
newans.push_back(ans[0]);
for(int i = 1;i < ans.size();i++){
if(ans[i] != ans[i-1]){
newans.push_back(ans[i]);
}
}
return newans;
}
};LeetCode 解答的想法：
解答直接將解延伸到 kSum 的問題，太狠了太狠了。
其實就是 two sums 以外的數，都使用巢狀迴圈來選取，剩下兩個數再用 two pointers 解 two sums 就可以了。
看完 Leetcode 的提示後，改進的 code ：
Runtime : 68 ms
Memory : 13.1 MB
保持著 "遇到相同的數，就再往下跳一格"的理念，可以避免重複的解。
但寫的方法有點醜…真正厲害的解法還請去 leetcode 的解答區觀賞了 ， leetcode 提供的解答透過遞迴的方式，實作出了 kSum 的 function 。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
if(nums.size() < 4){
return ans;
}
sort(nums.begin(), nums.end());
for(int i = 0;i < nums.size()-3;){
target -= nums[i];
for(int j = i+1;j < nums.size()-2;){
target -= nums[j];
int left = j + 1;
int right = nums.size()-1;
while(left < right){
int sum = nums[left] + nums[right]; // 當 sum == target 時，left 需要 + 1 ， right 需要 - 1。因為這題不允許有相同的解，所以才會用一個 while 迴圈，當 nums[left] == nums[left - 1] 時，就要繼續 left++;
// right 也需要做差不多的處理。
if(sum == target){
ans.push_back({nums[i], nums[j], nums[left], nums[right]});
left++;
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
right--;
while(left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if(sum < target){
left++;
while(left < right && nums[left] == nums[left - 1]) {
left++;
}
} else {
right--;
while(left < right && nums[right] == nums[right + 1]) {
right--;
}
}
}
target += nums[j];
j++;
while(j < nums.size() - 2 && nums[j] == nums[j - 1]) {
j++;
}
}
target += nums[i];
i++;
while(i < nums.size() - 3 && nums[i] == nums[i - 1]) {
i++;
}
}
return ans;
}
};
Sum 系列題目 ：
好...好多，這還不是全部 XD。
