一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 632|回复: 3
收起左侧

[Leetcode] 4Sum: Output Limit Exceeded

[复制链接] |试试Instant~ |关注本帖
see_world 发表于 2015-3-15 17:27:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
之前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;
    }
}
stellari 发表于 2015-3-15 21:49:37 | 显示全部楼层
话说,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.                        do lo ++; while (lo < hi && num[lo] == num[lo - 1]) ;
  31.                        do hi --; while (lo < hi && num[hi] == num[hi + 1]) ;
  32.                     }
  33.                 }
  34.             }

  35.         }
  36.         return all_res;
  37.     }
复制代码

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| see_world 发表于 2015-3-17 11:16:20 | 显示全部楼层
stellari 发表于 2015-3-15 21:49
话说,4Sum的函数声明可是有两个参数的:
vector fourSum(vector &num, int target)
你默认target为0真的 ...

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

使用道具 举报

chaozc 发表于 2015-3-19 20:38:59 | 显示全部楼层
光神你竟然还发这么学术的帖子。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表