有序数组的平方：双指针法的巧妙应用

在处理已排序数组的平方问题时，最直观的策略是先对所有元素进行平方操作，随后调用排序算法。这种方法的时间复杂度通常为 $O(N \log N)$。另一种常见的思路是寻找正负数的分界点，将数组拆分为负数和正数两个独立部分，反转负数部分后再与正数部分进行归并。虽然这能将时间复杂度降至 $O(N)$，但代码逻辑繁琐，且需要分配额外的内存空间。

更优雅且高效的解法是利用双指针技术。由于原数组是非递减排序的，平方后的最大值必然出现在数组的两端（即最左侧的负数或最右侧的正数）。我们可以设置两个指针，分别指向数组的首尾，通过比较两个指针所指元素的平方值，将较大的值从后往前依次填入结果数组中。

std::vector<int> sortedSquares(const std::vector<int>& numbers) {
    int n = numbers.size();
    std::vector<int> squaredResult(n);
    int leftPtr = 0;
    int rightPtr = n - 1;
    int insertPos = n - 1;

    while (leftPtr <= rightPtr) {
        int leftSquare = numbers[leftPtr] * numbers[leftPtr];
        int rightSquare = numbers[rightPtr] * numbers[rightPtr];

        if (leftSquare > rightSquare) {
            squaredResult[insertPos--] = leftSquare;
            ++leftPtr;
        } else {
            squaredResult[insertPos--] = rightSquare;
            --rightPtr;
        }
    }
    return squaredResult;
}

长度最小的子数组：滑动窗口机制解析

寻找和大于等于特定目标值的最短连续子数组时，暴力枚举所有可能的子数组会导致 $O(N^2)$ 的时间复杂度。如果在暴力法基础上尝试优化，例如引入复杂的前缀和计算或反向遍历，不仅容易产生重复计算，还会因为内存访问不连续而降低CPU缓存命中率，导致实际运行性能不佳。

滑动窗口（Sliding Window）是解决此类连续子数组问题的标准范式。通过维护一个动态的窗口区间，不断向右扩张窗口的右边界以累加元素值。当窗口内的元素和满足目标条件时，记录当前窗口长度，并尝试向右收缩窗口的左边界，以探索是否存在更短的满足条件的子数组。这种机制确保了数组中的每个元素最多被访问两次，从而将时间复杂度严格控制在 $O(N)$。

#include <vector>
#include <limits>
#include <algorithm>

int minSubArrayLen(int targetSum, const std::vector<int>& elements) {
    int minLength = std::numeric_limits<int>::max();
    int currentSum = 0;
    int windowStart = 0;

    for (int windowEnd = 0; windowEnd < elements.size(); ++windowEnd) {
        currentSum += elements[windowEnd];

        while (currentSum >= targetSum) {
            int currentLength = windowEnd - windowStart + 1;
            minLength = std::min(minLength, currentLength);
            currentSum -= elements[windowStart];
            ++windowStart;
        }
    }

    return (minLength == std::numeric_limits<int>::max()) ? 0 : minLength;
}