大家好！😊 欢迎来到“C++上岸”系列的第19期——算法篇！算法是面试中的硬核关卡，掌握好这些经典问题，能让你在笔试和面试中游刃有余。今天，我们精选了10道高频算法题，涵盖双指针等核心思想。我会逐一详细解答，包括算法思路和C++代码实现。🔥准备好了吗？让我们开始吧！

---

1. 移动零

要求：原地将数组中的零移到末尾，保持非零元素顺序。
思路：双指针法。指针left标记非零元素位置，遍历数组，遇到非零元素就交换到left处。

void moveZeroes(vector<int>& nums) {
    for (int left = 0, i = 0; i < nums.size(); i++) {
        if (nums[i] != 0) swap(nums[left++], nums[i]);
    }
}

时间复杂度：$O(n)$，空间复杂度：$O(1)$。
（假装有图）

---

2. 比较含退格的字符串

要求：#代表退格，判断两字符串是否相等。
思路：重构字符串（模拟栈）。遇到非#入栈，遇到#出栈。

bool backspaceCompare(string s, string t) {
    return build(s) == build(t);
}
string build(string str) {
    string res;
    for (char c : str) {
        if (c == '#') { if (!res.empty()) res.pop_back(); }
        else res.push_back(c);
    }
    return res;
}

时间复杂度：$O(n)$，空间复杂度：$O(n)$。

---

3. 有序数组的平方

要求：非递减数组平方后仍非递减。
思路：双指针从两端向中间遍历，比较平方值。

vector<int> sortedSquares(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    vector<int> res(nums.size());
    for (int i = nums.size() - 1; i >= 0; i--) {
        if (abs(nums[left]) > abs(nums[right])) {
            res[i] = nums[left] * nums[left];
            left++;
        } else {
            res[i] = nums[right] * nums[right];
            right--;
        }
    }
    return res;
}

时间复杂度：$O(n)$。

---

4. 长度最小的子数组

要求：和≥s的最短连续子数组长度。
思路：滑动窗口。右指针扩张，左指针收缩。

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, sum = 0, minLen = INT_MAX;
    for (int right = 0; right < nums.size(); right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left++];
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

时间复杂度：$O(n)$。

---

5. 水果成篮

要求：最多收集两种水果的最大连续数量。
思路：滑动窗口+哈希表记录水果类型数。

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> basket;
    int left = 0, maxFruits = 0;
    for (int right = 0; right < fruits.size(); right++) {
        basket[fruits[right]]++;
        while (basket.size() > 2) {
            if (--basket[fruits[left]] == 0) basket.erase(fruits[left]);
            left++;
        }
        maxFruits = max(maxFruits, right - left + 1);
    }
    return maxFruits;
}

时间复杂度：$O(n)$。

---

6. 最小覆盖子串

要求：s中包含t所有字符的最短子串。
思路：滑动窗口+双哈希表（需求窗口+当前窗口）。

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    int left = 0, valid = 0, start = 0, minLen = INT_MAX;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            char d = s[left++];
            if (need.count(d)) {
                if (window[d] == need[d]) valid--;
                window[d]--;
            }
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

时间复杂度：$O(n)$。

---

7. 螺旋矩阵 II

要求：生成顺时针螺旋的 $n\times n$ 矩阵。
思路：模拟螺旋路径，控制边界。

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n));
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int num = 1;
    while (num <= n * n) {
        for (int i = left; i <= right; i++) matrix[top][i] = num++;
        top++;
        for (int i = top; i <= bottom; i++) matrix[i][right] = num++;
        right--;
        for (int i = right; i >= left; i--) matrix[bottom][i] = num++;
        bottom--;
        for (int i = bottom; i >= top; i--) matrix[i][left] = num++;
        left++;
    }
    return matrix;
}

示例：n=3 → [[1,2,3],[8,9,4],[7,6,5]]。

---

8. 螺旋遍历二维数组

要求：返回二维数组的螺旋遍历结果。
思路：同问题7，按层模拟方向。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) return {};
    int m = matrix.size(), n = matrix[0].size();
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    vector<int> res;
    while (res.size() < m * n) {
        for (int i = left; i <= right; i++) res.push_back(matrix[top][i]);
        top++;
        for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]);
        right--;
        if (top <= bottom) {
            for (int i = right; i >= left; i--) res.push_back(matrix[bottom][i]);
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]);
            left++;
        }
    }
    return res;
}

---

9. 区间求和

要求：多次查询数组区间和。
思路：前缀和预处理。

int main() {
    int n;
    cin >> n;
    vector<int> nums(n), prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
        prefix[i + 1] = prefix[i] + nums[i];
    }
    int l, r;
    while (cin >> l >> r) {
        cout << prefix[r + 1] - prefix[l] << endl; // [l, r]区间和
    }
}

时间复杂度：查询 $O(1)$，预处理 $O(n)$。

---

10. 土地价值最小差

要求：横向或纵向切割网格，使两区域价值和差最小。
思路：枚举切割线 + 前缀和优化。

int minDifference(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    // 计算行前缀和
    vector<vector<int>> rowSum(n, vector<int>(m + 1, 0));
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < m; j++) 
            rowSum[i][j + 1] = rowSum[i][j] + grid[i][j];
    
    int total = 0, minDiff = INT_MAX;
    for (auto& row : grid) 
        for (int val : row) 
            total += val;
    
    // 枚举横向切割
    for (int i = 1; i < n; i++) {
        int sumTop = 0;
        for (int k = 0; k < i; k++) sumTop += rowSum[k][m];
        minDiff = min(minDiff, abs(2 * sumTop - total));
    }
    // 枚举纵向切割（类似）
    // ...
    return minDiff;
}

关键点：预处理行列前缀和，减少重复计算。

---

总结

本期涵盖了双指针、滑动窗口、前缀和、螺旋矩阵四大核心考点。面试前背熟这些代码，通过率+50%！💯
彩蛋：遇到“水果成篮”这类题，心里默念：“滑动窗口，yyds！” 🍉🍇

恭喜你坚持到了最后！🎉 本期我们覆盖了10道经典算法题，包括双指针等核心思想。掌握这些，能让你在C++面试中脱颖而出。算法学习重在实践，建议多写代码和模拟测试。如果你有疑问或想讨论，欢迎留言！😊 下期见，继续“C++上岸”之旅！🔥