3sum （C++代码）

解题思路:

先对数列排序。两个指针i,j;分别指向x+1(当前数字的后一位),j指向最后位置，如果a[i]+a[j]+a[x]<0;i++.如果a[i]+a[j]+a[x]>0,j++;相等count++;

注意事项:

对字符串的输入处理，要先对数列排序，遍历到数列长度-3即可。对于相同数字的，要跳过，避免重复

参考代码:

# include <cstdio>

# include <iostream>

# include <cstring>

# include <algorithm>

using namespace std;

char str[100001];

int a[100001];

int k=0;

void dealstr()

{

int len=strlen(str);

for(int i=0;i<len;i++)

{

if(str[i]!=' ')

{

int t=1;

int num=0;

while(str[i]!=' '&&str[i]!='\0')

{

if(str[i]=='-')

{

t=-1;

}

else

{

num=num*10+(str[i]-'0');

}

i++;

}

a[k++]=t*num;

}

}

}

int main()

{

int count=0;

gets(str);

dealstr();

sort(a,a+k);

for(int x=0;x<k-3;x++)

{

if(x!=0&&a[x]==a[x-1]) continue;

int i=x+1;

int j=k-1;

while(i<j)

{

while(a[i]+a[j]+a[x]<0&&i<j)

      i++;

while(a[i]+a[j]+a[x]>0&&j>i) 

  j--;

if(a[i]+a[j]+a[x]==0&&i!=j) 

{

count++;

i++;

while(i<j&&a[i-1]==a[i])

{

i++;

}

j--;

while(i<j&&a[j+1]==a[j])

{

j--;

}

}

}

} 

printf("%d\n",count);

return 0;

 }