题解 | 两数之和

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @param target int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

typedef struct {
    int value;
    int index;
} Element;

int compare (const void* a, const void* b) {
    return ((Element*)a)->value - ((Element*)b)->value;
}

int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // // 时间复杂度为O(n2)
    // // 分配内存存储结果
    // int* result = (int*)malloc(2 * sizeof(int));
    
    // for (int i = 0; i < numbersLen - 1; i++) {
    //     for (int j = i + 1; j < numbersLen; j++) {
    //         if (numbers[i] + numbers[j] == target) {
    //             result[0] = i + 1;
    //             result[1] = j + 1;
    //             // 设置返回数组的大小为2
    //             *returnSize = 2;
    //             return result;
    //         }
    //     }
    // }
    
    // // 理论上不会执行到这里，因为题目保证有解
    // *returnSize = 0;
    // return NULL;



    // O(nlogn)使用排序+双指针
    // 用分治 qsort进行排序
    Element* elements = (Element*)malloc(sizeof(Element)*numbersLen);
    for (int i=0; i<numbersLen; i++) {
        elements[i].index = i+1;
        elements[i].value = numbers[i];
    }

    qsort(elements, numbersLen, sizeof(Element), compare);

    int low = 0, high = numbersLen-1;
    int* result = (int*)malloc(sizeof(int)*2);
    while(low < high) {
        int sum = elements[low].value + elements[high].value;
        if (sum == target) {
            // 确保返回的索引是升序
            if (elements[low].index <= elements[high].index) {
                result[0] = elements[low].index;
                result[1] = elements[high].index;
            } else{
                result[0] = elements[high].index;
                result[1] = elements[low].index;
            }

            *returnSize = 2;
            free(elements);
            return result;
        } else if (sum > target) {
            high --;
        } else {
            low ++;
        }
    }


    *returnSize = 0;
    free(elements);
    return NULL;
}