一道算法题时间复杂度的优化分析

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

1
2
3
4
示例:
  给定 nums = [2, 7, 11, 15], target = 9
  因为 nums[0] + nums[1] = 2 + 7 = 9
  所以返回 [0, 1]

OK！题已给出，经过思考，给定目标值，在数组中，元素间两两相加等于目标，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标
 *
 * @param nums   数组
 * @param target 目标值
 * @return 返回下标数组
 */
public static int[] twoSumFor(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (target == nums[i] + nums[j]) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

上面一段代码分析：

  • 第一层for循环：对数组中每个元素进行遍历；
  • 第二次for循环内：将元素两两相加与目标值进行比较；
  • 由于是双层循环，这段代码时间消耗就是n*n的复杂度，时间复杂度为O(n^2)；
  • 空间复杂度方面，主要体现在计算过程，对于存储资源的消耗情况，都是在一个数组中，因此空间复杂度为O(1)。

代码优化

完成代码的分析后，发现时间复杂度为O(n^2)，经过思考，是不是还可以降低时间复杂度呢？首先想到是，是否有多余的代码可以删除，但是经过分析后，发现没有冗余无效的代码，这时想要优化，就要考虑使用采用一些数据结构进行处理了，把时间复杂度转移到空间复杂度。

上面的代码是两层for循环，那能否使用一个for循环进行优化呢？又回到题上，需要操作对象是数组的元素，返回数组的下标，这时发现，元素和元素的下标是不是有对应关系呢？灵光一闪，对应关系，key-value的值，额……这不就是字典吗，将元素和下标转换为一个字典，在对这个字典进行遍历，判断目标值减去元素值的值是否在字典中，就完成了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标
 *
 * @param nums   数组
 * @param target 目标值
 * @return 返回下标数组
 */
public static int[] twoSumPlus(int[] nums, int target) {
    // 声明HashMap，用来存在遍历数组的元素和下标{key(元素):value(下标)}
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        // 判断temp的值是否包含在map中
        if (map.containsKey(temp)) {
            return new int[]{map.get(temp), i};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

通过优化，发现之前两层for循环，成功的变为了一个for循环，因此：

  • 一个for循环，时间复杂度为O(n)
  • 定义了 k-v 字典，其字典元素的个数取决于输入数组元素的个数，空间复杂度为O(n)