4Sum: Output Limit Exceeded

之前3Sum也有这个报错，原因是没跳过重复元素。现在4Sum我觉得能优化的都考虑了，还是报Output Limit Exceeded，弄了近俩小时，整个人都不好了。于是在此求大神指导，感激不尽！
P.S.：我用的是O(N^3)的算法。
P.S.：含调试部分，所以请不要在意那个static。

附源代码如下：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    static vector<vector<int> > fourSum(vector<int> &num) {
        vector<vector<int> > ans;
        int len=num.size();
        if(len<4)
            return ans;
        qsort(num, 0, len-1);
        if(num[0]>0 || num[len-1]<0)
            return ans;
        for(int i=0; i<len-4 && num[i]<=0; i++){
            if(i!=0 && num[i]==num[i-1])
                continue;
            for(int j=i+1; j<len-3; j++){
                if(j!=i+1 && num[j]==num[j-1])
                    continue;
                int l=j+1, r=len-1;
                while(l<r){
                    int temp=num[i]+num[j]+num[l]+num[r];
                    if(temp<0){
                        while(l<r-1 && num[l]==num[l+1])l++;
                        l++;
                    }
                    else if(temp>0){
                        while(l<r-1 && num[r]==num[r-1])r--;
                        r--;
                    }
                    else{
                        vector<int> vt;
                        vt.push_back(num[i]);
                        vt.push_back(num[j]);
                        vt.push_back(num[l]);
                        vt.push_back(num[r]);
                        ans.push_back(vt);
                        while(l<r-1 && num[l]==num[l+1])l++;
                        l++;
                        while(l<r-1 && num[r]==num[r-1])r--;
                        r--;
                    }
                }
            }
        }
        return ans;
    }
    static void qsort(vector<int> &n, int l, int r){
        if(l>=r)
            return;
        int mid=(l+r)/2;
        int pl=l, pr=r, x=n[mid];
        n[mid]=n[l];
        while(pl<pr){
            while(pl<pr&&n[pr]>=x)
                pr--;
            if(pl<pr)
                n[pl]=n[pr];
            while(pl<pr&&n[pl]<=x)
                pl++;
            if(pl<pr)
                n[pr]=n[pl];
        }
        n[pl]=x;
        qsort(n,l,pl);
        qsort(n,pr+1,r);
    }
};
int main(){
    vector<int> v;
    for(int i=0; i<2; i++){
        v.push_back(-i-1);
    }
    for(int i=0; i<2; i++){
        v.push_back(i+1);
    }
    for(int i=0; i<2222; i++){
        v.push_back(0);
    }
    vector<vector<int> > ans;
    ans=Solution::fourSum(v);
    for(int i=0; i<ans.size(); i++){
        vector<int> vtemp=ans.at(i);
        for(int j=0; j<vtemp.size(); j++)
            cout<<vtemp[j]<<" ";
        cout<<endl;
    }
}

话说，4Sum的函数声明可是有两个参数的：
vector<vector<int> > fourSum(vector<int> &num, int target)
你默认target为0真的没问题吗？

另外，个人认为这段代码略显臃肿；附一段我自己的代码做参考。
---------------

1. vector<vector<int> > fourSum(vector<int> &num, int target) {
   
2.         int nnum = num.size();
   
3.         vector<vector<int> > all_res;
   
4.         vector<int> res(4, 0);
   
5.         
   
6.         sort(num.begin(), num.end());
   
7.         for (int i = 0;i < nnum - 3; i ++)
   
8.         {
   
9.             if (i > 0 && num[i] == num[i-1]) continue;
   
10.             res[0] = num[i];
    
11.             
    
12.             int subtarget1 = target - num[i];
    
13.             for (int j = i + 1; j < nnum -2; j ++)
    
14.             {
    
15.                 if (j > i + 1 && num[j] == num[j-1]) continue;
    
16.                 res[1] = num[j];
    
17.                
    
18.                 int subtarget2 = subtarget1 - num[j];
    
19.                 int lo = j + 1;
    
20.                 int hi = nnum - 1;
    
21.                 while (lo < hi)
    
22.                 {
    
23.                     if (num[lo] + num[hi] > subtarget2) hi--;
    
24.                     else if (num[lo] + num[hi] < subtarget2) lo++;
    
25.                     else  // If num[lo] + num[hi] == subtarget2
    
26.                     {
    
27.                         res[2] = num[lo];
    
28.                         res[3] = num[hi];
    
29.                         all_res.push_back(res);
    
30. 
    
31.                        do lo ++; while (lo < hi && num[lo] == num[lo - 1]) ;
    
32.                        do hi --; while (lo < hi && num[hi] == num[hi + 1]) ;
    
33.                     }
    
34.                 }
    
35.             }
    
36. 
    
37.         }
    
38.         return all_res;
    
39.     }

复制代码

stellari 发表于 2015-3-15 21:49
话说，4Sum的函数声明可是有两个参数的：
vector fourSum(vector &num, int target)
你默认target为0真的 ...

丢脸了、、、对，少个target的参数，白瞎我俩小时了TT。。。
我们的思路是一样的，你写的稍微清楚些~
加上target稍微改一下就好啦，至于之前为什么exceed依然不明就里。
非常感谢！

光神你竟然还发这么学术的帖子。。