1、题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

2、解答思路

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        // 按照规范，这里的HashMap应定义长度len-1
        // key: nums[i] value: i
        Map<Integer,Integer> hashTable = new HashMap<Integer, Integer>(len-1);

        for(int i = 0;i<len;i++){
        	// 去哈希表中查找是否有target-nums[i]存在，若有则返回结果，否则将其存到哈希表中
            if(hashTable.containsKey(target-nums[i])) {
            	// 无需定义一个新的变量，直接返回new的对象即可
            	return new int[] {i, hashTable.get(target-nums[i])};
            }
            hashTable.put(nums[i], i);
        }
        // 若不存在，则抛出异常或任意返回值
        return new int[0];
    }
}

• 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
• 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。