关于我：微信公众号：面试官问，原创高质量面试题，始于面试题，但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目。
本文是力扣的第一题，两数之和，大家读完题目后，应该都可以很快写出时间复杂度为 O(n²)，空间复杂度 O(1) 的解法，也就是暴力解法（Brute Force）：
class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length; for (int i=0; i<len; ++i) { for (int j=i+1; j<len; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[]{-1, -1}; }}
复制代码
当然，两层 for 循环嵌套的代码写起来一时爽，但这并不是一个高效的解法，性能很低，面试官也不会满意，因此，我们需要进一步思索更优的解法，看看是否可以通过空间换时间来降低代码的执行耗时，例如可以通过哈希表来记录元素值到元素所在索引的映射关系，并利用哈希表 O(1) 的查找时间来降低时间复杂度。如下所示：
class Solution { public int[] twoSum(int[] nums, int target) { // 哈希表的 key 是 nums[i]，value 是 i Map<Integer, Integer> cache = new HashMap<>();
// 输入数组长度 int len = nums.length;
// 初始化哈希表 for (int i=0; i<len; ++i) { cache.put(nums[i], i); }
for (int i=0; i<len; ++i) { // 两数之和 sum 转换成首先固定一个数 A，那另外一个数就是 another = sum-A int another = target - nums[i]; // 如果 another 也在哈希表中，且不是 nums[i] 时，说明找到两数之和的另外一个数 if (cache.containsKey(another) && i != cache.get(another)) { return new int[]{i, cache.get(another)}; } }
// 没有找到符合条件的两个数，我们返回异常值即可 return new int[]{-1, -1}; }}
复制代码
代码提交后，我们发现结果并不理想：
特别是内存消耗方面，因为代码中我们用了两次 for 循环，那是否可以把它们合并成一次呢？因为我们看到，在上面第二个 for 循环中使用 cache 哈希表时，只会使用到当前循环位置 i 及之前的数据，不会使用到还没有循环到的数据，因此，提前在第一个 for 循环中初始化 cache，其实没有必要，可以进行合并，此外，符合条件的两个元素 x，y 肯定是一前一后出现的，如果存在符合条件的 target，在遍历到 x 时，哈希表里没有符合的 y，此时把 x 加入到了哈希表里，当后面遍历到 y 时，就可以在哈希表里找到对应的 x 了，只不过是先找到还是后找到的问题，所以只需要一次遍历即可，如下所示我们把 cache 的赋值直接挪动到 for 循环的第一行：
for (int i=0; i<len; ++i) { // 初始化哈希表 cache.put(nums[i], i);
// 两数之和 sum 转换成首先固定一个数 A，那另外一个数就是 another=sum-A int another = target - nums[i];
// 如果 another 也在哈希表中，且不是 nums[i] 时，说明找到两数之和的另外一个数 if (cache.containsKey(another) && i != cache.get(another)) { return new int[]{i, cache.get(another)}; }}
复制代码
提交后，发现答案不对😅，在执行用例 nums = [3,3], target=6 时出错，也就是符合条件的两个元素值相等，会导致 if (cache.containsKey(another) && i != cache.get(another)) 这个条件不成立，因此，需要把 cache 的赋值挪动到 if 判断后面去，完整代码如下：
class Solution { public int[] twoSum(int[] nums, int target) { // 哈希表的 key 是 nums[i]，value 是 i Map<Integer, Integer> cache = new HashMap<>();
// 输入数组长度 int len = nums.length;
for (int i=0; i<len; ++i) { // 两数之和 sum 转换成首先固定一个数 A，那另外一个数就是 another=sum-A int another = target - nums[i];
// 如果 another 也在哈希表中，且不是 nums[i] 时，说明找到两数之和的另外一个数 if (cache.containsKey(another) && i != cache.get(another)) { return new int[]{i, cache.get(another)}; }
// 初始化哈希表 cache.put(nums[i], i); }
// 没有找到符合条件的两个数，我们返回异常值即可 return new int[]{-1, -1}; }}
复制代码
执行结果如下所示，空间和时间都有所改善，但不明显，目前的时间复杂度是 O(N)。
除了上面两种解法，是否还有其他解法呢？是更优还是较差？例如，是否可以将数组排序，然后使用双指针法进行遍历，如下所示：
class Solution { public int[] twoSum(int[] nums, int target) { // 先将数组排好序 Arrays.sort(nums);
// 算出数组长度 int len = nums.length;
// 左指针指向数组开头，并逐步往中间移动 int left = 0; // 右指针指向数组末尾，并逐步往中间移动 int right = len - 1;
// 开始循环 while (left < right) { int sum = nums[left] + nums[right]; if (target == sum) { // 找到后，返回两数在数组中的下标 return new int[]{left, right}; } else if (target < sum) { // 当两数之和大于目标值时，由于数组已经从小到大排序，因此，右指针要往中间移动 right--; } else if (target > sum) { // 当两数之和小于目标值，由于数组已经从小到大排序，因此，左指针要往中间移动 left++; } }
return new int[]{-1, -1}; }}
复制代码
提交后，发现答案在某些用户是错误的，代码逻辑应该没有问题，百思不得其解。通过仔细阅读题目描述，是要求我们返回两个元素的下标，而我们在一开始 Arrays.sort(nums) 对数组排序时，就已经把原来数组的下标位置给修改了，因此在这道题的背景下，排序+双指针法没法使用，以失败告终。这个教训也告诉我们，不要一错再错，一开始方向错了，那后面再怎么努力也是白费的，人生亦是如此！
当然，如果我们把题目要求的返回满足条件的两个元素的数组下标改为返回两个元素，那就可以使用上面的排序+双指针解法。这个解法 while 循环的时间复杂度是 O(N)，而排序的时间复杂度是 log(N)，因此总的时间复杂度是 O(NlogN)。
评论