力扣每日一题：两数之和

简介：

今天开始每天刷一道力扣题目，把自己的答案与官方答案进行对比，找出自己的不足，提高代码的质量

题目描述


我的解题过程

思路

1. 遍历整个数组，依次将数组中的每一个值nums[i]作为第一个num
2. 再次遍历数组，从j = i + 1开始遍历，在数组中寻找是否有某个值等于target - num
3. 找到就break，找不到就抛异常

一开始为了减少判断次数，我认为两个数都是小于等于target的，所以我先判断nums[i]是不是小于target，小于就continue，就不用执行后面的代码了，这样可以节省不少时间

但是当我提交的时候，发现自己忽略了负数，这就导致另一个非负数可以大于target的情况，有点考虑不周

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
      	//res用来保存两个索引值
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                res[0] = i;
                if ((target - nums[i]) == nums[j]){
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
}

代码复杂度分析

时间复杂度：代码进行了两次for循环，因此时间复杂度是O(n²)

空间复杂度：开辟了两个单元的数组res保存结果，空间复杂度为O(1)

官方解题过程

思路

1. 先用for循环遍历数组，将nums[i]作为第一个数值
2. 如果再去遍历一次数组来找另一个值效率太低，选择引用查找效率极高的哈希表来找第二个值

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
          	//注意i不能重复，所以&&后面的代码要加上
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

代码复杂度分析

时间复杂度：引入了查找速度为O(1)哈希表，查找效率大大提升，只用了一层for循环，时间复杂度为O(n)

空间复杂度：因为引入了哈希表，因此空间复杂度变为O(n)，以空间换时间

总结

1. 暴力求解法，代码执行时间为70ms左右，引入哈希表时间为3ms左右
2. 所以涉及到查找的算法，如果在空间充足的情况下，可以引用哈希表来大大优化时间
3. 上面是官方给出的第二种解法，这种解法不能解决数组中有重复值得情况，如果有重复值就需要第三种解法了