MIOJ #15 和为零的三元组

描述

给出一个整数数组, 数组中是否存在任意 3 个数 a, b, c 满足 a + b + c = 0? 找出数组中所有满足以上条件的三元组,最后输出这些三元组的个数(包含相同元素的三元组只计算一次)。

输入

一个包含多个整数(正或负)的字符串,每个整数之间用逗号(,)分隔,如:-1,0,1,2,-1,-4。

输出

输入满足加和结果正好等于 0 的三元组的个数,如对于 -1,0,1,2,-1,-4 有 [-1, 0, 1] 和 [-1, -1, 2],所以输出 2

输入样例

-1,0,1,2,-1,-4

输出样例

2

AC代码:

#include <bits/stdc++.h>
#include<vector>
#include<stack>
#include<sstream>
using namespace std;

int main()
{
    int k ;
    int num;
    string s;
    while(cin>>s)
    {
        bool symbol = true;
        vector<int>a(0);
        int result = 0;
        s = s+",";
        bool flag = false;
        int b = 0;
        int j = 0;
        int k = 0;
        int a1 = 0;
        int cnt = 0;
        int temp = -1;
        for(int i = 0; i<s.length(); i++)
        {
            flag = false;
            b = 0;
            k = j;
            if(s[i] =='-'){
                symbol = false;
                i++;
            }
            if(s[i] ==',')
            {
                if(s[k] =='-'){
                symbol = false;
                k++;
            }
                while(k != i)
                {
                    b = b*10+(s[k]-48);
                    k++;
                }
                flag = true;
                j = i+1;
            }
            if(flag == true)
            {
                if(symbol == false){
                    b = b*(-1);
                    symbol = true;
                }
                a.push_back(b);


            }
        }
        sort(a.begin(),a.end());
        for(int i = 0;i<a.size()-2;i++){
                if(a1 == a[i] && i!= 0){//防止重复
                    continue;
                }
            a1 = a[i];
            int temp1 = i+1;
            int temp2 = a.size()-1;
            while(temp1 < temp2){
                    if(a[temp1]+a[temp2] + a1==0){
                       // cout<<a1<<" temp1:"<<temp1<<" temp2:"<<temp2<<endl;
                        result ++;
                        while(a[temp1] == a[temp1+1]){//防止重复
                            temp1++;
                        }
                        while(a[temp2] == a[temp2-1]){//防止重复
                            temp2++;
                        }
                        temp1++;
                        temp2--;
                    }
                    else if(a[temp1]+a[temp2] + a1>0){
                        temp2--;
                    }
                    else if(a[temp1]+a[temp2] +a1<0){
                        temp1++;
                    }
            }
        }
        cout<<result<<endl;
    }
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注