two sums三种实现c语言

以下是三种不同的 C 语言实现 Two Sum 问题的方法：

方法 1：暴力枚举

这种方法的思路很简单，就是使用两个嵌套循环，枚举所有可能的组合，找到符合条件的组合。

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, j;
    int *result = NULL;
    *returnSize = 0;
    result = (int*)malloc(2 * sizeof(int));
    for(i = 0; i < numsSize - 1; i++){
        for(j = i + 1; j < numsSize; j++){
            if(nums[i] + nums[j] == target){
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    return result;
}

方法 2：哈希表

这种方法使用哈希表来记录已经遍历过的数，在遍历到新的数时，检查哈希表中是否存在与之匹配的数。若存在，则找到了答案；若不存在，则将该数加入哈希表中。

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i;
    int *result = NULL;
    *returnSize = 0;
    result = (int*)malloc(2 * sizeof(int));
    int hash[numsSize];
    memset(hash, -1, sizeof(hash));
    for(i = 0; i < numsSize; i++){
        int numToFind = target - nums[i];
        if(hash[numToFind] != -1){
            result[0] = hash[numToFind];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        hash[nums[i]] = i;
    }
    return result;
}

方法 3：排序+双指针

这种方法先将数组排序，然后使用双指针在已排好序的数组中查找符合条件的数对。

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i = 0, j = numsSize - 1;
    int *result = NULL;
    *returnSize = 0;
    result = (int*)malloc(2 * sizeof(int));
    int *numsCopy = (int*)malloc(numsSize * sizeof(int));
    memcpy(numsCopy, nums, numsSize * sizeof(int));
    qsort(numsCopy, numsSize, sizeof(int), cmp);
    while(i < j){
        if(numsCopy[i] + numsCopy[j] == target){
            for(int k = 0; k < numsSize; k++){
                if(nums[k] == numsCopy[i]){
                    result[0] = k;
                    break;
                }
            }
            for(int k = numsSize - 1; k >= 0; k--){
                if(nums[k] == numsCopy[j]){
                    result[1] = k;
                    break;
                }
            }
            *returnSize = 2;
            break;
        }
        else if(numsCopy[i] + numsCopy[j] < target){
            i++;
        }
        else{
            j--;
        }
    }
    free(numsCopy);
    return result;
}

int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}