浅滩


私信TA

用户名:bob2048

访问量:1996

签 名:

人傻就该多读书

等  级
排  名 169
经  验 2911
参赛次数 2
文章发表 31
年  龄 0
在职情况
学  校
专  业 计算机科学与技术

  自我简介:

烦死了

问题 A: 3sum

时间限制: 1Sec 内存限制: 128MB 提交: 53 解决: 3

题目描述

给定n个整数,在这n个数中找出所有存在a、b、c元素使得a + b + c = 0?在数组中找到所有唯一的三元组,它们的和为零。

输入

给你一组有重复数字(每一个数据不超过|1000|)的数据,以空格隔开

输出

输出有多少组唯一的三元组(重复的三元组算一组)

样例输入

-1 0 1 2 -1 -4

样例输出

2

代码如下:

#include "iostream"
using namespace std;
int main()
{
 
 int arrary[100],size=0;
 int book[1000][3],num=0;//标记数组 
 for(int i=0;i<100;i++)
 arrary[i]=INT_MAX;
 while(cin >> arrary[size])
 {
 size++;
 }
 for(int i=0+0;i<size-2;i++)//不计重复只要满足条件直接标记 
 {
 for(int j=i+1;j<size-1;j++)
 for(int k=j+1;k<size-0;k++)
 {
 if(arrary[i]+arrary[j]+arrary[k]==0)
 {
    book[num][0]=arrary[i];book[num][1]=arrary[j];book[num][2]=arrary[k];
    num++;
    //cout<< arrary[i] <<"+"<< arrary[j]<<"+"<< arrary[k] <<"=0\n"<<i << " "<<j<<" "<<k<<"\n";测试时用的 
}
 }
 
 }
 
 for(int i=0;i<num-1;i++)//去重 
 {
 for(int j=i+1;j<num;j++){
      if(book[i][0]==book[j][0]&&book[i][1]==book[j][1]&&book[i][2]==book[j][2]) num--;
 else if(book[i][0]==book[j][0]&&book[i][1]==book[j][2]&&book[i][2]==book[j][1]) num--;
 else if(book[i][0]==book[j][1]&&book[i][1]==book[j][0]&&book[i][2]==book[j][2]) num--;
 else if(book[i][0]==book[j][1]&&book[i][1]==book[j][2]&&book[i][2]==book[j][0]) num--;
 else if(book[i][0]==book[j][2]&&book[i][1]==book[j][1]&&book[i][2]==book[j][0]) num--;
 else if(book[i][0]==book[j][2]&&book[i][1]==book[j][0]&&book[i][2]==book[j][1]) num--;
}
 }
 cout << num;
}


C语言网提供「C语言、C++、算法竞赛」在线课程,全部由研发工程师或ACM金牌退役选手亲自授课,以视频+配套题目的学练同步模式教学,强化动手,并提供增值服务!

  评论区