怎么理解时间复杂度和空间复杂度？

时间复杂度：指算法语句的执行次数。

空间复杂度：就是一个算法在运行过程中临时占用的存储空间大小，换句话说就是被创建次数最多的变量，它被创建了多少次，那么这个算法的空间复杂度就是多少。有个规律，如果算法语句中就有创建对象，那么这个算法的时间复杂度和空间复杂度一般一致，很好理解，算法语句被执行了多少次就创建了多少对象。

题目要求

原题链接：两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

1
2
3
4
5
class Solution {
    public int[] twoSum(int[] nums, int target) {

    }
}

示例 1：

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

示例 2：

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

示例 3：

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

题解

方法一：暴力枚举

直接 双层for循环 暴力枚举，唯一需要注意的是，内层循环是从外层往后开始遍历的，即外层循环从 i=0 的下标开始，内层循环就需要 i下标 往后一位，从 i+1 开始，用时大约 58 ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 双层for循环，外层从0下标往后
        for (int i = 0; i <= nums.length; i++) {
            // 内层每次从i+1下标往后
            for (int j = i + 1; j < nums.length; j++) {
                // 招到结果返回
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        // 没找到结果返回
        return new int[0];
    }
}

方法二：哈希表

方法一慢在哪里了呢，当我们确定了外层循环的值后 nums[i]，我们需要通过遍历的方法确定是否存在对应的那个值，满足 nums[i]+nums[j]=target，时间消耗在了这里

那么改进的方法就是通过哈希表来优化，nums[i] 确定的情况下，到底有没有那个满足要求的nums[j]，即 target - nums[i] 是否存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 建立一个哈希表
 * 以数组中元素的值为key，数组中元素的下标为value
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>(16);
        for (int i = 0; i < nums.length; i++) {
            // 判断哈希表中是否存在 target - nums[i] 的key
            if (hashMap.containsKey(target - nums[i])) {
                // 如果存在说明两数之和为target，返回两个正数的下标
                return new int[]{hashMap.get(target - nums[i]), i};
            }
            // 存入哈希表中，key为正数数组的值，value为对应的下标
            hashMap.put(nums[i], i);
        }
        return new int[0];
    }
}