【一道简单的算法题】希望有创新的

设计一个时间复杂度为O(n)的算法：
给定一个含有n个整数的数组A和一个整数x,
该算法判断A中是否存在有两个和等于x的元素。

8 个解决方案

#1

如果数组A 不是已经排序好的话貌似没有 O(n)的算法
排序好了的话就首位双指针查

#2

Hash就可以了

#3

做个标记，

#4

无序的话不行吧

#5

贴上自己写的一段代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int _g_array[] = {1,2,3,4,5,6,7,8,9,10};


bool func(int _array[],int _length,int _x)
{
	bool _ret = false;
	int *_pt_tmp = (int *)malloc(_x*sizeof(int));
	if ( !_pt_tmp )
		return _ret;

	memset(_pt_tmp,0,sizeof(_x*sizeof(int)));

	for ( int i = 0;i < _length;++i )
		_pt_tmp[_array[i]%_x] += 1;

	if ( _pt_tmp[0] >= 2 )
		_ret = true;
	else if ( _x%2 == 0 )
	{
		if ( _pt_tmp[(_x+1)/2] >= 2 )
			_ret = true;
	}
	else
	{
		for ( int i = 1;i < (_x + 1)/2;++i )
		{
			int j = _x - i;
			if ( _pt_tmp[i] && _pt_tmp[j] )
			{
				_ret = true;
				break;
			}
		}
	}

	free(_pt_tmp);
	return _ret;
}

int main()
{
	printf("%d\r\n",func(_g_array,10,19));
	getchar();
	return 0;
}

#6

引用 2 楼 litaoye 的回复:

Hash就可以了

hash=x-A[i]，不过一般的hash(比如取余)还不如排序

#7

引用 5 楼 yg2362 的回复:

贴上自己写的一段代码

C/C++ code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int _g_array[] = {1,2,3,4,5,6,7,8,9,10};


bool func(int _array[],int _length,int _x)
{
    bool _……

代码写的好专业啊

#8

就是，我瞬间以为看见了库函数