LeetCode刷题-1两数之和

1. 题目

//给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 
//
// 示例: 
//
// 给定 nums = [2, 7, 11, 15], target = 9
//
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
// 
// Related Topics 数组 哈希表

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        
    }
}
//leetcode submit region end(Prohibit modification and deletion)

2. 思路

看到这个题，首先想到最搓的方式就是嵌套 for 循环，当然如果使用最搓的方法那就没什么意义了。在写业务代码的时候，我们都要切记尽量避免嵌套循环，更何况是做算法题。

那既然时间复杂度过高，我们是不是可以想办法用空间换时间呢？

我们想，如果在遍历数组的时候，用 target 减去这个元素的值，即 rightNum = target - num[i]，其中 rightNum 为答案中的一个元素，num[i] 为另一个。如果我能直接通过 rightNum 的值找到 rightNum 所对应的位置，并且时间复杂度为 O(1) 的话，那么总的时间复杂度不就是 O(1) 了嘛，问题不就解决了吗？

这不就是典型的 key-value 的形式吗？作为一个 Java 程序员，首先脑海里想到的不就是 HashMap 吗？HashMap 底层是数组，支持随机访问，通过 key 去查找 value 的时间复杂度就是 O(1) 。

想到 HashMap 之后，解答就很简单了，遍历数组，以 num[i] 为 key , i 为 value ，存入 HashMap 中，如果 rightNum 命中了 HashMap 中的某个 key 。则找到了答案，直接返回。

来，上代码：

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

3. 结合实际项目

在我们做分布式系统的项目时，假设有下面一种场景出现。运营提需求说，我们现在后台要拉一份的订单记录，记录里面要包含下单用户的信息，比如手机号，住址等等，要给下单量大的用户发礼物。这个时候我们要怎么做呢？订单表 join 用户表？肯定不是的，分布式系统中可能库都是分开的，没法 join 。

一般我们订单表中，肯定会维护 userId ，记录是谁下的单，那么我们在查出的订单记录中取出所有的 userId ，得到一个 List 集合。然后用户系统会提供一个服务，传参是 userId 的 List 集合，返回的数据是用户信息对象集合，信息包含上面的手机号、地址等等。

这时候我们就得到了两个集合，一个订单的 List ，一个用户的 List ，难道我们要嵌套循环，最终组装成一个 List 返回给客户端吗？

当然不是，我们会构造一个 HashMap , key 是 userId , value 是用户信息对象。

然后遍历用户的 List ，依次塞到 HashMap 中。

最后遍历订单的 List ，从 HashMap 中取出订单所属 userId 对应的用户信息对象。

小结：无论是这道算法题，还是实际业务使用，其本质都是利用 HashMap 获取某个 key 对应 value 值得时间复杂度为 O(1) 。而 HashMap 的本质是数组这种数据结构支持随机访问。