NC61.两数之和 C语言 双指针法

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

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

int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) {
    // 分配结果数组
    int* result = (int*)malloc(2 * sizeof(int));
    // 复制原数组
    int* nums_cpy = (int*)malloc(numbersLen * sizeof(int));
    for (int i = 0; i < numbersLen; i++) {
        nums_cpy[i] = numbers[i];
    }
    // 排序
    qsort(nums_cpy, numbersLen, sizeof(int), cmp);
    // 双指针查找
    int left = 0, right = numbersLen - 1;
    int sum;
    while (left < right) {
        sum = nums_cpy[left] + nums_cpy[right];
        if (sum == target) {
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    // 在原数组中查找下标
    int i, j;
    for (i = 0; i < numbersLen; i++) {
        if (numbers[i] == nums_cpy[left])
            break;
    }
    for (j = numbersLen - 1; j >= 0; j--) {
        if (numbers[j] == nums_cpy[right])
            break;
    }
    // 设置返回结果（下标从1开始）
    if (i < j) {
        result[0] = i + 1;
        result[1] = j + 1;
    } else {
        result[0] = j + 1;
        result[1] = i + 1;
    }
    *returnSize = 2;
    // 释放临时内存
    free(nums_cpy);

    return result;
}