讨论/题目交流/两数之和 以 5w 为分界 4ms 8mb/
两数之和 以 5w 为分界 4ms 8mb

代码如下, 为什么以5w为分界 5w以下使用哈希表 5w以上使用暴力搜索 能够达到优化
是测试用例刚刚好还是有什么原因```
50000的数值是, 随着数据量变大, 哈希表所用时间上升

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* rel = (int* )malloc(2*sizeof(int));
    *returnSize = 2;
    //创建结果集
    int min = INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < min) min = nums[i];
    }
    //搜索最小数
    int max = target - min;
    int len = max - min + 1; //数组偏移, 下标0对应0+min
    if (len <= 50000) {
        int* hash = (int* )malloc(len * sizeof(int));

        for (int i = 0; i < len; i++) {
            hash[i] = -1;
            //hash内存放互补数的下标, 下标最小为0, 所以用-1初始化
        }

        for (int j = 0; j < numsSize; j++) {
            if (nums[j] <= max) {
                int n = nums[j] - min; //数组下标偏移量min
                if (hash[n] != -1) {
                    rel[0] = hash[n];
                    rel[1] = j;
                }
                hash[target - nums[j] - min] = j; //数组下标偏移量min
            }
        }
        free(hash);
    } else {
        int flag = true;
            
        for (int i = 0; i < numsSize; i++) {
            for (int j = i+1; j < numsSize; j++) {
                if (flag && target == nums[j] + nums[i]) {
                    rel[0] = i;
                    rel[1] = j;
                    flag = false;
                }
            }
        }
    }
    return rel;
}

展开讨论
共 0 个讨论
无讨论