Leetcode - 1. 两数之和

class Solution {

    // 以测试用例 nums = [2,7,11,15], target = 9 为例，要找到答案，就需要遍历数组
    // 第一个元素为2，那么我们自然想知道数组中是否有元素7（即2的补数）；如果有，它对应的下标是多少
    // 如何找到补数？最简单的方法是暴力法，直接再遍历一遍数组，查看补数是否存在
    // 也可以将数字作为键、对应的下标作为值存入map中，然后通过其get()方法找某个数字在原数组中的下标
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;

        // historyMap用于存储已经遍历过的元素及其对应的下标
        Map<Integer, Integer> historyMap = new HashMap<>(len << 1);
        
        // 遍历数组中的元素
        for(int i = 0; i < len; i++){
            int num = nums[i];

            // 如果能在历史记录里找到补数，则直接返回当前下标与补数的下标
            Integer complementIndex = historyMap.get(target - num);
            if (complementIndex != null) {
                return new int[] {complementIndex, i};
            }
            
            // 否则将当前数与下标存到历史记录表中
            historyMap.put(num, i);
        }

        // 题目说有且只有一个答案，所以一定不会执行到这里
        return new int[0];
    }
}