有大佬解释一下这代码什么原理吗

[stevenbipt]

刷 leetcode 时翻了一下以前刷的题发现一个神奇的代码，题目是 leetcode 第一题两数之和，本来以为用 hash 表做已经达到极限了，结果发现了一个更快的代码，由于个人能力有限分析不出全部代码的精明之处，求大佬们指点。 java 代码： class Solution { public int[] twoSum(int[] nums, int target) { int numMin = Integer.MAX_VALUE; int numMax = Integer.MIN_VALUE; for (int num : nums) { if (num < numMin) { numMin = num; }

    if (num > numMax) {
      numMax = num;
    }
  }  
  int max = target - numMin;
  int min = target - numMax;

  int targetMax = max > numMax ? numMax : max;
  int targetMin = min < numMin ? numMin : min;  
  int[] numIndices = new int[targetMax - targetMin + 1];

  for (int i = 0; i <= numIndices.length - 1; i++) {
    numIndices[i] = -1;
  }    
  for (int i = 0; i <= nums.length - 1; i++) {
    if (nums[i] >= targetMin && nums[i] <= targetMax) {
      int offset = -targetMin;
      if (numIndices[(target - nums[i]) + offset] != -1) {
        return new int[] { numIndices[(target - nums[i]) + offset], i };
      } else {
        numIndices[nums[i] + offset] = i;
      }
    }
  }
  return new int[] { 0, 0 };
}

}

[pandaaa]

排版啊少年→_→

[stevenbipt]

@pandaaa 没搞懂这个代码怎么排版出来的= =

[stevenbipt]

class Solution {
public int[] twoSum(int[] nums, int target) {

int numMin = Integer.MAX_VALUE;
int numMax = Integer.MIN_VALUE;
for (int num : nums) {
if (num < numMin) {
numMin = num;
}

if (num > numMax) {
numMax = num;
}
}
int max = target - numMin;
int min = target - numMax;

int targetMax = max > numMax ? numMax : max;
int targetMin = min < numMin ? numMin : min;

int[] numIndices = new int[targetMax - targetMin + 1];

for (int i = 0; i <= numIndices.length - 1; i++) {
numIndices[i] = -1;
}
for (int i = 0; i <= nums.length - 1; i++) {
if (nums[i] >= targetMin && nums[i] <= targetMax) {
int offset = -targetMin;
if (numIndices[(target - nums[i]) + offset] != -1) {
return new int[] { numIndices[(target - nums[i]) + offset], i };
} else {
numIndices[nums[i] + offset] = i;
}
}
}
return new int[] { 0, 0 };
}
}

[stevenbipt]

完啦更鬼畜了= =妈耶

[lhx2008]

这个代码现在直接提交会更快吗，历史的不算数的

[stevenbipt]

@lhx2008 不会，就是 3ms，上次看到最快的是用 hash 表完成的（ 6ms)

[lcdtyph]

这就是实现了一个哈希函数是 hash(x) -> x 的哈希表啊。
而且这个代码在数据极差很大的时候肯定会 MLE

[stevenbipt]

@lcdtyph 谢谢大佬指点(｡･∀･)ﾉﾞ

[stevenbipt]

@lcdtyph 弱弱问大佬一句（ mle 什么意思啊= =）

[lcdtyph]

@stevenbipt #9 MLE 是 memory limit error 就是内存超限，TLE 就是时间超限

[stevenbipt]

@lcdtyph 谢谢大佬指点😚😚😚

[lcdtyph]

@stevenbipt 啊…是 memory limit exceeded 抱歉

[DeweyLiu]

@stevenbipt 哈希 好像 1ms 就搞定了

[vegito2002]

自己拿数组造轮子做 stack 做 map 的解法， 就是用来耍 OJ 玩的， 大概了解一下就行了， 真正面试的时候不会碰到这么蛋疼的公司的。

[stevenbipt]

@DeweyLiu 貌似在 java 上最快就 3ms