【LeetCode】1. 两数之和(Java自用版)

哈希表法：

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

上面的Java代码是一个有效的解决方案，用于在整数数组nums中找到两个数的索引，使得它们的和等于给定的目标值target。下面是对该代码的详细分析：

1. 初始化哈希表：
   代码首先创建了一个HashMap（hashtable），其中键是数组中的数字，值是对应数字的索引。这个哈希表用于存储已经遍历过的数组元素，以便在后续的迭代中快速查找它们的补数（即目标值减去当前元素的值）。

Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();

2. 遍历数组：
   代码通过for循环遍历数组nums。对于每个元素nums[i]，它执行以下操作：

for(int i = 0; i < nums.length; i++) {

3. 查找补数：
   在循环内部，代码计算target - nums[i]（即当前元素的补数），然后检查哈希表中是否包含这个补数。

if(hashtable.containsKey(target - nums[i])) {

如果哈希表中存在这个补数，那么它表示已经找到了一个解，即nums[i]和补数对应的元素，它们的和等于target。此时，代码创建一个包含这两个元素索引的整数数组，并返回它。

return new int[] {hashtable.get(target - nums[i]), i};

4. 更新哈希表：
   如果哈希表中不存在补数，代码将当前元素nums[i]及其索引i添加到哈希表中，以便在后续的迭代中查找。

hashtable.put(nums[i], i);

5. 返回空数组：
   如果遍历完整个数组后都没有找到满足条件的两个数，那么代码返回一个空的整数数组。

return new int[0];

总结：
这个twoSum方法利用哈希表实现了O(n)时间复杂度的算法，其中n是数组nums的长度。由于哈希表的查找操作平均时间复杂度为O(1)，因此整个算法的效率非常高。这个算法的关键在于利用哈希表来存储已经遍历过的元素，以便快速查找它们的补数。这种方法比使用嵌套循环来比较所有可能的元素对要高效得多。