讨论/题目交流/关于“两数之和”问题耗时0ms那个提交的疑惑/
关于“两数之和”问题耗时0ms那个提交的疑惑

这几天有空的时候看了看题库,入门第一题,两数之和,以我的水平也就是双层循环了,然后开始看别人的答案,HashMap的方法我觉得挺好,耗时也少(至少系统检测结果是这样)
然后翻着翻着又发现个耗时 0ms的提交,又专门去提交记录里找了一下,还真有,然后开始看实现方法。。

class Solution {
    public int[] twoSum(int[] nums, int target) { 
        int volume =2048; //100000000000 
        int bitMode = volume-1;//011111111111 
        int [] result =new int[volume];

        for (int i=0;i<nums.length;i++){
        int c = (target - nums[i]) & bitMode;
        if (result[c]!=0){
            return new int[]{result[c]-1,i};
        }
        result[nums[i] & bitMode]=i+1;
    }
    return null;
    }
}

凭我依稀记得的那点大学学的计算机知识,某个值和 bitMode(2047)做 “与” 操作,结果其实就是对volume(2048)取余,hash好像也是这样的操作吧(不知道有没有理解错)
这里就想到有冲突了怎么办,我看评论里有人说 hash遇到冲突后会转成循环(老实说我也不懂,反正就是有冲突了会处理),而代码里好像没处理,那会不会有错呢??
通过多次尝试,发现输入的值如果是volume的整数倍,就会有问题。

    int[] input = {2048,4096,6144,8192};
    int target = 8192;
    /**
      类似这样的输入, 执行结果是[0,1],但实际上应该是[0,2]
        target是volume的整数倍,输入的数组中有两个或两个以上的数也是volume的整数倍,这个方法就会把前两个整数倍数字的下标输出 */

至此,问题是hash冲突造成的?还有这个0ms,官方是不是考虑提高一下时间精度。。。leetcode.gif

展开讨论
七个夏命吧发起于 2020-05-20
最近编辑于 2020-05-20

感谢反馈,0 ms 不是平台的问题,是用户代码跑得快,有随机因素的。感谢对力扣网站的支持。