两数之和

LeetCode第一题

题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

思路

1.暴力算法，用两个循环计算两个数之和是否为目标值
但是写出代码之后，逻辑上没问题，就是编译通不过。后来查看了其他人的代码，发现returnSize被赋值了。因为看不到主函数是怎么写的，所以不清楚其怎样调用并输出结果。我尝试着将他给的模板中的形式参数int * returnSize去掉，执行时就提示传入的参数过多。那么就说明一定要按他给的模板来写，其中有多少个形参就要用多少个。
源码如下：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
        int i = 0;
        int j = 0;
        int *q=(int *)malloc(sizeof(int) * 2);
        *returnSize = 2;

    for(i = 0;i < numsSize - 1;++i){
        for(j = i + 1;j < numsSize;++j){
            if((nums[i] + nums[j]) == target){
                q[0] = i;
                q[1] = j;
                return q;
            }
        }
    }

    return 0;
}

2.先排序再双指针求和
第二种思路就是先对数组元素由大到小排序。排序算法选择快排，这样时间复杂度就低一点。然而结果需要返回两个数的下标，所以我新建一个数组用来保存数字在原始数组中的下标。排序之后，利用双指针从首尾向中间夹击，就能在O（n）的复杂度找出所需的两个数，再在其下标数组中获得其原始下标即可。
综合起来此算法的时间复杂度为O（nlogn）。
源码如下：

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *sub = (int *)malloc(sizeof(int) * numsSize);
    int i = 0;
    for(i = 0;i < numsSize;++i){
        sub[i] = i;
    }
    *returnSize = 2;
    int *p = (int *)malloc(sizeof(int) * 2);
    QuickSort(nums,0,numsSize-1,sub);
    int beg = 0;
    int end = numsSize - 1;
    while(beg < end){
        if((nums[beg] + nums[end]) < target){
            ++beg;
        }
        else if((nums[beg] + nums[end]) > target){
            --end;
        }
        else{
            p[0] = sub[beg];
            p[1] = sub[end];
            return p;
        }
    }
    return 0;

}
//采用快排先对数组进行由小到大排序，建立一个大小和原数组一样的数组，用来保存元素的原始下标

int Partiotion(int *a,int low,int high,int *sub){
    int privot = a[low];
    int sub_0 = sub[low];
    while(low < high){
        while(low < high && a[high] >= privot) --high;
        a[low] = a[high];
        sub[low] = sub[high];
        while(low < high && a[low] <= privot) ++low;
        a[high] = a[low];
        sub[high] = sub[low];
    }
    a[low] = privot;
    sub[low] = sub_0;
    return low;
}

void QuickSort(int *A,int low,int high,int *sub){
    if(low < high){
        int privotpos = Partiotion(A,low,high,sub);
        QuickSort(A,low,privotpos - 1,sub);
        QuickSort(A,privotpos + 1,high,sub);
    }
}

此算法的缺点在于需要创建下标数组，空间复杂度提高了。