【C语言】【8ms】Leetcode 1.两数之和

【C语言】【8ms】Leetcode 1.两数之和

目录

题目描述

思路及效果

代码

---

题目描述

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

       你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

       你可以按任意顺序返回答案。

思路及效果

 思路：先对原数组进行排序，再用两个分别指向首尾的下标指针s和t查找那两个整数，如果target-st，则s++，如果==则找到了。但要返回的是原数组里的下标，此处用的方法是另开排序数组，最后找到答案后再遍历找原数组下标。

 效果：速度比较快（主要是快排处的时间），但因为复制了数组用于排序，牺牲了内存。

代码

        感觉写得还是有点复杂化了...不美啊

        写代码这里有个坑：Leetcode给的主函数里的returnSize参数是要返回你找的结果数组里的元素个数，我刚开始还以为是用这个作为结果数组返回，一直结果不对。实际结果数组应另定义新的。

int cmp(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    //先排序，然后前后找
    int * sort_nums = (int *)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++){
        sort_nums[i] = nums[i];
    }
    qsort(sort_nums, numsSize, sizeof(int), cmp);
    int s = 0, t = numsSize - 1;
    while (s < t) {
        int s_val = sort_nums[s], t_val = sort_nums[t];
        int u_val = target - s_val;
        if (u_val == t_val) {
            int u1 = 0, u2 = 0;
            int * result = (int *) malloc (2 * sizeof(int));
            for (int i = 0; i < numsSize; i++) {
                //循环内是将排序后的数组与原数组下标map
                if (sort_nums[s] == nums[i] && u1 == 0) {
                    result[0] = i;
                    u1 = 1;
                    continue;
                }
                if (sort_nums[t] == nums[i] && u2 == 0) {
                    result[1] = i;
                    u2 = 1;
                }
            }
            *returnSize = 2;
            return result;
        }
        else if (u_val < t_val)t--;
        else s++;
    }
    * returnSize = 0;
    return NULL;
}