# Demo entry 3548629

yuhao

Submitted by anonymous on Jan 13, 2016 at 22:55
Language: C++. Code size: 3.6 kB.

```//
//  KCGQ4.cpp
//
//  Created by Yuhao on 1/10/16.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

//define variables for use
int N(0),i(0),j(0),leftPointer(0),rightPointer(0),sumThree(0),tempInput(0);

//reads a sequence of numbers from standard input
//example input: "-1 -1 0 2 -2 -3 5;"
//notice that the sequence should end with a ";"
vector<int> seq;
cout<<"Please enter the sequence with integers separated by space and ended with ';'"<<endl;
while(cin>>tempInput){
seq.push_back(tempInput);
}

//sort the sequence into ascending order
sort(seq.begin(),seq.end());
N=(int)seq.size();

//initialize vector for storing solutions
vector<vector<int>> solution;
vector<int> tempVector(3);

//search for triples
for (i=0;i<N;i++){
//check whether the current first element is the same as the previous one
if((i==0) || (i>0 && seq[i] != seq[i-1])){
//initialize two pointers for rest two elements
leftPointer=i+1;
rightPointer=N-1;

//search for rest two elements in triple, only need O(N) time as the sequence is sorted
while (leftPointer<rightPointer){
sumThree=seq[i]+seq[leftPointer]+seq[rightPointer];

if (sumThree>0){
//sum exceeds zero, need smaller element
rightPointer=rightPointer-1;
}
else if(sumThree<0){
//sum less than zero, need larger element
leftPointer=leftPointer+1;
}
else{
//solution found, save solution
tempVector[0]=seq[i];
tempVector[1]=seq[leftPointer];
tempVector[2]=seq[rightPointer];
solution.push_back(tempVector);

while((leftPointer+1)<rightPointer && seq[leftPointer]==seq[leftPointer+1]){
leftPointer=leftPointer+1;
}
leftPointer++;

while((rightPointer-1)>leftPointer && seq[rightPointer]==seq[rightPointer-1]){
rightPointer=rightPointer-1;
}
rightPointer--;
}
}
}
}

//Print out solutions found
if (solution.size()==0){
cout<<"No solution found!"<<endl;
}
else{
for (i=0;i<solution.size();i++){
cout<<"No."<<(i+1)<<" triple: ";
for (j=0;j<3;j++){
cout<<solution[i][j]<<" ";
}
cout<<endl;
}
}

//sample outputs:
//
//Please enter the sequence with integers separated by space and ended with ';'
//1 -1 0 2 -2 -3 5;
//No.1 triple: -3 -2 5
//No.2 triple: -3 1 2
//No.3 triple: -2 0 2
//No.4 triple: -1 0 1

return 0;
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.