4 Values whose Sum is 0

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2²⁸ ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

//用二分查找后面两个的和与前面两个的和是否相加等于0
#include<iostream>
#include<algorithm>
using namespace std;
#define N 4000
#define M 16000000
int a[N],b[N],c[N],d[N],ab[M],cd[M];
int main()
{
    int n,i,j,k,l,r,mid,cnt,ablen,cdlen;
    while(cin>>n)
  {
    cnt=ablen=cdlen=0;
    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
   //求前面两个数的和
    for(i=0;i<n;i++)
    {
         for(j=0;j<n;j++)
         {
               ab[ablen++]=a[i]+b[j];
         }

    }
     //求后面两个数和的相反数
    for(i=0;i<n;i++)
    {
         for(j=0;j<n;j++)
         {
             cd[cdlen++]=-c[i]-d[j];
         }
    }
    sort(cd,cd+cdlen);
    for(i = 0;i < ablen;i++)
    {
        l=0;
        r=cdlen-1;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(cd[mid]==ab[i])
            {
                cnt++;
                //可能出现有相同的数字，所以往后继续找！
                for(k=mid+1;k<cdlen;k++)
                {
                  if(cd[k]!=ab[i])
                         break;
                   else
                         cnt++;
                }
              //可能出现有相同的位置在前面，所以往前找
                for(k=mid-1;k>=0;k--)
                {
                    if(cd[k]!=ab[i])
                         break;
                    else
                          cnt++;
                }

                break;
            }
            if(cd[mid]<ab[i])
            {
                 l=mid+1;
            }
            else
            {
                r=mid-1;
            }
       }
    }
    cout<<cnt<<endl;
  }
    return 0;
}


//用Hash的话，时间复杂度降低。空间复杂度提升，也就是用空间换时间

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 4010
#define p 15999991
using namespace std;
int a[MAX][4];
int h[MAX*MAX];  //hash table
int f[MAX*MAX];  //对应hash table 中数的个数
void hash(int a)
{
     int key;
     key = (a % p + p)%p;
    while( (f[key]>0) && (h[key]!=a)) 
      key = (key+1)%p;

    f[key]++;
    h[key]=a;
}
int find(int a)
{
     int key ;
     key = (a % p + p)%p;
 while((f[key]>0)&&(h[key]!=a))
     key = (key+1)%p;
    return f[key] ;
}
int main()
{
   int i,n,j;
  while(cin>>n)
  {
     for(i=0;i<n;i++)
     {
          cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
     }
     memset(f,0,sizeof(f));
     for(i=0;i<n;i++)
     {
          for(j=0;j<n;j++)
          {
              hash(a[i][0]+a[j][1]);
          }
     }
     int ans = 0;
     for(i=0;i<n;i++)
     {
          for(j=0;j<n;j++)
          {
             ans += find(-(a[i][2]+a[j][3]));
          }
     }
      cout<<ans<<endl;
  }
     return 0;
}