two sums三种实现C语言完整代码及主函数

下面是三种不同的实现方式：

方式一：时间复杂度 O(n^2)，空间复杂度 O(1)

void twoSum(int* nums, int numsSize, int target, int* returnSize){
    for(int i=0; i<numsSize; i++){
        for(int j=i+1; j<numsSize; j++){
            if(nums[i]+nums[j] == target){
                returnSize[0] = i;
                returnSize[1] = j;
                return;
            }
        }
    }
}

方式二：时间复杂度 O(nlogn)，空间复杂度 O(n)

struct Node{
    int val, idx;
};

int cmp(const void* a, const void* b){
    return ((struct Node*)a)->val - ((struct Node*)b)->val;
}

void twoSum(int* nums, int numsSize, int target, int* returnSize){
    struct Node* arr = (struct Node*)malloc(sizeof(struct Node)*numsSize);
    for(int i=0; i<numsSize; i++){
        arr[i].val = nums[i];
        arr[i].idx = i;
    }
    qsort(arr, numsSize, sizeof(struct Node), cmp);
    int left = 0, right = numsSize-1;
    while(left < right){
        if(arr[left].val + arr[right].val == target){
            returnSize[0] = arr[left].idx;
            returnSize[1] = arr[right].idx;
            free(arr);
            return;
        }
        else if(arr[left].val + arr[right].val < target){
            left++;
        }
        else{
            right--;
        }
    }
    free(arr);
}

方式三：时间复杂度 O(n)，空间复杂度 O(n)

void twoSum(int* nums, int numsSize, int target, int* returnSize){
    int hash[100000] = {0};
    for(int i=0; i<numsSize; i++){
        if(hash[target-nums[i]] != 0){
            returnSize[0] = hash[target-nums[i]]-1;
            returnSize[1] = i;
            return;
        }
        hash[nums[i]] = i+1;
    }
}

主函数调用示例：

#include <stdio.h>

int main(){
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize[2] = {0};
    twoSum(nums, sizeof(nums)/sizeof(int), target, returnSize);
    printf("[%d, %d]\n", returnSize[0], returnSize[1]);
    return 0;
}