题目：两数之和

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

解答

解法一：简单遍历

看到题目，直接暴力两遍遍历数组

加入小优化：j从后往前遍历，且不遍历i已经遍历过的元素

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length-1; j > i; j--){
                if(target == (nums[i] + nums[j])) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

时间复杂度：O(n²) ，加入的优化不改变本质。

解法二：Hash表存储

因为每种输入都只会对应一个答案，所以可以得知数组中元素不会重复。可以用以下结构的Hash表：

• key：数组的元素
• value：数组元素对应下标

再遍历一次数组，用target-元素的值作为key查询Hash表，找到则返回即可。

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

时间复杂度：O(N)，具体来说是2N；

解法二优化

可以将第一个创建hashMap的循环优化掉，在一个循环中同时判断与创建hashMap

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

时间复杂度：O(N)，只需要遍历一次！

小结

从今天（2024-09-09）开始从零开始从头刷leetcode-hot100，时隔一年刷算法题的感觉就是

智能编译器太好用了啊！没有编译器疯狂编译错误，几个小编码错误：

• 定义HashMap时候，=前面用接口的声明（Map），后面才是具体实现类，这样可以让代码更灵活且具有可扩展性，因为可以随时更换具体的实现类，而不需要更改变量的类型声明。对象定义基本上都是遵循的这样的原则：
  • 【面向接口编程的原则】代码依赖于抽象（接口）而不是具体的实现（实现类）
• 尽管 int 是 Java 中的基本数据类型，但 int[] 数组属于引用类型。数组在 Java 中是对象，因此 int[] 数组变量实际上是指向数组对象的引用。数组需要使用 new 来创建内存空间，例如：
  • int[] arr = new int[5];
  • 所有的数组，无论是基本类型还是引用类型的数组，都是引用类型。