1. 两数之和 [简单]

数组哈希表

题目链接：

https://leetcode.cn/problems/two-sum/

方案一：

解题思路：

• 前提：nums中只会有一组有效答案
• 针对这样的题目，自然想到的是写两个循环来分别寻找x和y

• 当然要注意第 2 个循环中的起始位置是 x+1

  解题代码：

  class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int x = 0; x < nums.length; x++) {
            for (int y = x + 1; y < nums.length; y++) {
                if (nums[x] + nums[y] == target) {
                    return new int[]{x, y};
                }
            }
        }
        return new int[0];
    }
  }

  运行结果：

  

  复杂度分析：

• 时间复杂度：O(n**2**)，两重循环，最差情况需要遍历 n * n 次

• 空间复杂度：O(1)，没有占用额外的空间

  方案二：

  进阶：你可以想出一个时间复杂度小于 O(n**2**) 的算法吗？

  解题思路：

• 从方案一的执行时间来看，两重循环还是太耗时了

• 那么新的思路就是如何减少嵌套循环
• 这里可以考虑用空间换时间，将遍历过的不满足要求的数据先存入 HashMap 中

• 每次遍历时判断HashMap中是否有满足条件的数据

  解题代码：

  class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                return new int[]{map.get(other), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
  }

  运行结果：

  

  复杂度分析：

• 时间复杂度：O(n)，这里只有一层循环了

• 空间复杂度：O(n)，HashMap会占用额外的空间

  引发的思考：

  从该题目的分类中，其实已经透露了方案二的解题思路，对于时间复杂度为O(n**2**)的优化策略，就是用空间换时间