leetcode第一题-two Sum

很快我的研一上半学期就愉快的结束了，感觉每天都在忙，但是就看不到成果。转眼间就到了下学期，实习与论文的压力接踵而至，原来也接触过一部分的OJ，但是总体做的不是很深，所以利用这个机会，好好的把leetcode的题目做一做，检测一下自己的算法能力以及重新拾起丢掉的编程感觉。

第一题是一个查找类型的题目，当我看到题目的时候，不就是找到两个下标嘛，直接双重循环，上代码：

#include<stdio.h>
#include<stdlib.h>


int *twoSum(int numbers[],int n,int target)
{
	int *index=(int*)malloc(sizeof(int)*2);
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=i;j<n;j++)
		{
			if(numbers[i]+numbers[j]==target)
			{
				index[0]=i+1;
				index[1]=j+1;
				break;
			}
			else
				continue;
		}
	}
	return index;
}

int main()
{
	int a[100],n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		int target;
		scanf("%d",&target);
		int *index=twoSum(a,n,target);
		printf("index1=%d,index2=%d\n",index[0],index[1]);
	}
	return 0;
}

#include<stdio.h>
#include<stdlib.h>

void swap(int *x,int *y)//交换两个数
{
	int tmp=*x;
	*x=*y;
	*y=tmp;
}

int binarySearch(int numbers[],int target,int low,int high)//二分查找
{
	if(low>high)
		return -1;
	int mid=(high-low)/2+low;
	if(target>numbers[mid])
		return binarySearch(numbers,target,mid+1,high);
	else if(target<numbers[mid])
		return binarySearch(numbers,target,low,mid-1);
	else
		return mid;
}


void sort(int numbers[], int orders[], int low, int high)
{
    int key, keyOrder, i, j, ran;
    if (low < high)
    {
        ran = (low + high) / 2;
        swap(&numbers[ran], &numbers[low]);
        swap(&orders[ran], &orders[low]);
        key = numbers[low];
        keyOrder = orders[low];
        i = low + 1;
        j = high;
        while (i <= j)
        {
            while ((i <= high) && (numbers[i] <= key))
                i++;
            while ((j >= low) && (numbers[j] > key))
                j--;
            if (i < j)
            {
                swap(&numbers[i], &numbers[j]);
                swap(&orders[i], &orders[j]);
            }

        }
        swap(&numbers[low], &numbers[j]);
        swap(&orders[low], &orders[j]);
        sort(numbers, orders, low, j - 1);
        sort(numbers, orders, j + 1, high);
    }

}
int *twoSum(int numbers[], int n, int target) 
{
    int i=0, j=-1;
    int *index =(int *)malloc(2*sizeof(int));
    int len = n;
    int *orders=(int *)malloc(n*sizeof(int));
    for(i=0;i<len;i++)
    {
        orders[i]=i+1;//记录的是每一个数字的位置
    }
    sort(numbers,orders,0,len-1);//实现排序
    for(i=0;i<len;i++)
    {
        j=binarySearch(numbers,target - numbers[i],i+1,len-1);//找到了另外一个数
        if(j>-1)
            break;
    }
    if(j>-1)
    {
        if(orders[i]>orders[j])
        {
            index[0]=orders[j];
			index[1]=orders[i];
        }
        else
        {
            index[0]=orders[i];
			index[1]=orders[j];
        }
        return index;
    }
    else
        return NULL;
}

int main()
{
	int a[100],n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		int target;
		scanf("%d",&target);
		int *index=twoSum(a,n,target);
		printf("index1=%d,index2=%d\n",index[0],index[1]);
	}
	return 0;
}

用了这两种实现，运行的时间只有5ms，也顺利的AC了。

leetcode第一题-two Sum

原文：http://blog.csdn.net/zyh920521/article/details/44591643