Space 两个总和的复杂性

Question

我写了一段两和的代码：

public static int[] twoSums0(int[] nums, int target){

    for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i] == target-nums[j]){
                return new int[]{i,j};
            }
        }
    }
    throw new IllegalArgumentException("No solution");
}

我只想知道，为什么 space 复杂度是 O(1)？为什么当我们使用 hashmap 时，它变成了 O(n)？

时间复杂度很容易理解，但我不明白 space 复杂度。

Answer 1

要计算 space 复杂度，您必须分析您的方法创建的所有对象和基元的渐近大小。您不包括输入的大小。

此方法最多创建一个包含 2 个元素的数组（除了用于循环索引的 2 个基元之外）。因此它需要常数 space（即 O(1) space 复杂度）。

如果您要使用 HashMap 来提高此方法的时间复杂度，我假设您会将输入数组的所有元素添加到 HashMap，这将需要O(n) space.

Space 两个总和的复杂性

Space complexity in two sums

java

algorithm

space-complexity