做过最蛋疼的OJ题目,TWO SUM

嗯,这里是简介,主题配置内可以修改,如留空则不显示

做过最蛋疼的OJ题目,TWO SUM

题目描述:给定一个单调不减的数列p和一个整数m,求有多少组a,b,满足pa+pb=m

输入

第一行一个整数T,表示有T组测试数据。

每组数据第一行是1个整数m。

第二行是整数n,表示p中有n个数字。

第三行是n个数字,表示p的所有元素。
T≤3,1≤n,m≤3∗106,0≤pi≤3∗106

输出:每组数据输出一个数x,表示满足条件的组数。

思路:其实很简单就是设置两个指针,但是时间总是超过两秒。首先使用STL的,然后使用数组,然后使用hash表。直接见代码吧。

1、直接使用STL的容器:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){     

	int M;
	cin>>M;

	int m[3];
	vector< vector<int> > intVV;
	vector<int> intV ;

	int n;
	for (int i=0; i<M; i++)
	{
		cin>>m[i]>>n;
		intV.clear();
		for (int j = 0; j<n; j++)
		{
			int temp;
			cin>>temp;
			intV.push_back(temp);
		}
		//cout<<intV.size()<<endl;
		intVV.push_back(intV);
	}

	//cout<<intVV.size()<<endl;;
	//for_each(intVV.begin(), intVV.end(), col);
	for (int ii=0; ii<intVV.size(); ++ii)
	{
		vector<int> v = intVV[ii];
		//cout<<v.size()<<endl;

		int l = 0;
		int r = v.size()-1;
		int num = 0;

		while(l<r){
			if (v[l] + v[r] == m[ii])
			{
				num++;
				++l;
			}else if (v[l] + v[r] < m[ii])
			{
				++l;
			}
			else if(v[l] + v[r] > m[ii])
			{
				--r;
			}
		}

		if (v.size()%2 == 0)
		{
			cout<<num*2<<endl;
		}else{
			if (v[v.size()/2]*2 ==m[ii])
			{
				cout<<num*2+1<<endl;
			}else{
				cout<<num*2<<endl;
			}
		}
	}

	return 0; 
 }

2、使用数组的方式

#include <iostream>
using namespace std;

int main(){     

	int M;
	cin>>M;

	int m[3];
	int s[3];
	int intVV[3][3000000];

	for (int i=0; i<M; i++)
	{
		cin>>m[i]>>s[i];
		for (int j = 0; j<s[i]; j++)
		{
			cin>>intVV[i][j];
		}
	}

	for (int ii=0; ii<M; ++ii)
	{

		int l = 0;
		int r = s[ii]-1;
		int num = 0;

		while(l<r){
			if (intVV[ii][l] + intVV[ii][r] == m[ii])
			{
				num++;
				++l;
			}else if (intVV[ii][l] + intVV[ii][r] < m[ii])
			{
				++l;
			}
			else if(intVV[ii][l] + intVV[ii][r] > m[ii])
			{
				--r;
			}
		}

		if (s[ii]%2 == 0)
		{
			cout<<num*2<<endl;
		}else{
			if (intVV[ii][s[ii]/2]*2 ==m[ii])
			{
				cout<<num*2+1<<endl;
			}else{
				cout<<num*2<<endl;
			}
		}
	}

	return 0; 
 }

3、使用hash的方法

#include <iostream>
using namespace std;

int main(){     

	int M;
	cin>>M;

	int m[3];
	int s[3];
	int intVV[3][1000]={0};
	int temp;

	for (int i=0; i<M; i++)
	{
		cin>>m[i]>>s[i];
		for (int j = 0; j<s[i]; j++)
		{
			cin>>temp;
			intVV[i][temp]++;
		}
	}

	for (int ii=0; ii<M; ++ii)
	{
		int l = 0;
		int r = 9;
		int sum = 0;

		while(l<=9 || r>=0)
		if (l+r == m[ii])
		{
			sum += (intVV[ii][l]*intVV[ii][r]);
			++l;
		}
		else if (l+r<m[ii])
		{
			++l;
		}
		else if (l+r>m[ii])
		{
			--r;
		}
		cout<<sum<<endl;
	}
	return 0; 
 }


4、改进的数组的方式

#include <iostream>
using namespace std;

int main(){     

	int M;
	cin>>M;

	int m[3];
	int s[3];
	int intVV[3][2000000];

	for (int i=0; i<M; i++)
	{
		cin>>m[i]>>s[i];
		for (int j = 0; j<s[i]; j++)
		{
			cin>>intVV[i][j];
		}
	}

	for (int ii=0; ii<M; ++ii)
	{

		int l = 0;
		int r = s[ii]-1;
		int num = 0;
		int sign = 0; 

		while(l<r){
			if (intVV[ii][l] + intVV[ii][r] == m[ii])
			{
				if (sign == 0)
				{
					int a = intVV[ii][l];
					while(intVV[ii][l++] == a) num++;
					l++;
				}
				else if (sign == 1)
				{
					int b = intVV[ii][r];
					while(intVV[ii][r--] == b) num++;
					r--;
				}
			}else if (intVV[ii][l] + intVV[ii][r] < m[ii])
			{
				++l;
				sign = 0;
			}
			else if(intVV[ii][l] + intVV[ii][r] > m[ii])
			{
				--r;
				sign = 1;
			}
		}

		if (s[ii]%2 == 0)
		{
			cout<<num*2<<endl;
		}else{
			if (intVV[ii][s[ii]/2]*2 ==m[ii])
			{
				cout<<num*2+1<<endl;
			}else{
				cout<<num*2<<endl;
			}
		}
	}

	return 0; 
 }





已有6位网友发表了看法:

4 2016-05-26 08:56:14 回复
测试都没法通过
yuanmouren1hao 2016-06-04 11:08:40 回复
@4 你好,是报什么错。

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Hello world. 豫ICP备16008819号-1.

Power by Z-BlogPHP  Theme by wzdaxue