今天还是来理解空间复杂度

其实就是开摆一天

当讨论空间复杂度时，我们可以通过具体的代码示例来说明不同情况下的空间复杂度。

示例 1: 常数空间复杂度 O(1)

void printNumber(int num) {
    int count = 0; // 常数级别的额外空间
    for (int i = 0; i < num; i++) {
        cout << i << endl;
        count++;
    }
}

在这个示例中，我们定义了一个额外的整数变量 count，但它的空间占用是固定的，与输入参数 num 的大小无关。因此，该函数的空间复杂度是 O(1)，即常数级别的空间复杂度。

示例 2: 线性空间复杂度 O(n)

void duplicateNumbers(const vector<int>& numbers) {
    unordered_set<int> duplicates; // 额外的线性空间
    for (int num : numbers) {
        if (duplicates.count(num) > 0) {
            cout << num << " is a duplicate number." << endl;
        } else {
            duplicates.insert(num);
        }
    }
}

在这个示例中，我们使用了一个无序集合 duplicates 来存储重复的数字。随着输入参数 numbers 的大小增加，集合的大小也会增加，因此额外空间的使用与输入规模成线性关系。因此，该函数的空间复杂度是 O(n)，即线性级别的空间复杂度。

示例 3: 对数空间复杂度 O(log n)

int binarySearch(const vector<int>& sortedArray, int target) {
    int left = 0;
    int right = sortedArray.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

在这个示例中，我们实现了一个二分查找算法。该算法的额外空间主要用于存储左边界和右边界的索引，它们的数量随着输入规模的增加而以对数方式增长。因此，该函数的空间复杂度是 O(log n)，即对数级别的空间复杂度。

让我们考虑一个更经典的问题：

计算斐波那契数列的第n个数字。

斐波那契数列是一个以0和1开始，后续每个数字都是前两个数字之和的数列。斐波那契数列的前几个数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, ...

我们将展示三种不同的解决方案，每种方案的空间复杂度不同。

常数空间复杂度解法（O(1)）：

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int prev = 0;
    int current = 1;
    for (int i = 2; i <= n; i++) {
        int temp = current;
        current = prev + current;
        prev = temp;
    }

    return current;
}

这个解法使用了常数级别的额外空间。我们使用两个变量 prev 和 current 来迭代计算斐波那契数列的下一个数字，只需使用常数个变量来存储中间结果。因此，该解法的空间复杂度是 O(1)。

线性空间复杂度解法（O(n)）：

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

这个解法使用了一个大小为 n+1 的数组 fib 来存储斐波那契数列的前 n 个数字。我们从 0 和 1 开始，迭代计算并存储每个数字。由于数组的大小与输入的 n 成线性关系，因此该解法的空间复杂度是 O(n)。

递归解法（指数空间复杂度）：

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

这个解法使用了递归来计算斐波那契数列的第 n 个数字。每次递归调用都会产生两个新的递归调用，因此递归树的大小与输入 n 成指数关系。因此，该解法的空间复杂度是指数级别的。

其实空间复杂度对于过题没有时间复杂度重要。

这样可能不是蛮清楚，我这里写上一个我以前写过的题，不优化空间就过不了。

题目可能记不得正确了，但大概是对的

"最大子数组和"问题

给定一个整数数组，我们需要找到具有最大和的连续子数组。

例如，对于数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组和为[4, -1, 2, 1]，其和为6。

如果不优化空间，我们可以使用动态规划来解决这个问题。下面是一个使用动态规划的解决方案，其空间复杂度为O(n)：

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n); // 创建一个大小为n的动态规划数组
    dp[0] = nums[0]; // 初始化第一个元素
    int maxSum = dp[0]; // 记录当前最大和

    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]); // 动态规划递推公式
        maxSum = max(maxSum, dp[i]); // 更新最大和
    }

    return maxSum;
}

在上面的解决方案中，我们使用了一个大小为n的动态规划数组dp来存储每个位置的最大子数组和。通过迭代计算每个位置的最大和，并不断更新最大和的值，最终得到最大子数组和。

然而，如果我们要优化空间复杂度，可以使用"滚动数组"的思想，将空间复杂度降低到O(1)。下面是一个使用滚动数组优化的解决方案：

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int prevSum = nums[0]; // 用于记录前一个位置的最大和
    int maxSum = prevSum; // 记录当前最大和

    for (int i = 1; i < n; i++) {
        prevSum = max(prevSum + nums[i], nums[i]); // 动态规划递推公式
        maxSum = max(maxSum, prevSum); // 更新最大和
    }

    return maxSum;
}