算法编程题：双指针与滑动窗口（8 题）

解题思路： 和过小时移动左指针，过大时移动右指针。

不变量： 每次移动都排除不可能与当前另一端组成目标和的一整行候选。

public static class AlgCode039Solution
{
    public static int[] Solve(int[] numbers, int target)
    {
        int left = 0, right = numbers.Length - 1;
        while (left < right)
        {
            long sum = (long)numbers[left] + numbers[right];
            if (sum == target) return [left, right];
            if (sum < target) left++;
            else right--;
        }
        return [];
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 负数；重复值；加法溢出；无解返回空数组。

面试追问：

• 如果输入无序，哈希方案的时间和空间是多少？

解题思路： 排序后固定一个值，对右侧区间使用相向双指针。

不变量： 固定值不变时，left/right 之外的候选已被单调排除。

public static class AlgCode040Solution
{
    public static int[][] Solve(int[] numbers)
    {
        int[] values = (int[])numbers.Clone();
        Array.Sort(values);
        var result = new List<int[]>();
        for (int first = 0; first < values.Length - 2; first++)
        {
            if (first > 0 && values[first] == values[first - 1]) continue;
            int left = first + 1, right = values.Length - 1;
            while (left < right)
            {
                long sum = (long)values[first] + values[left] + values[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else
                {
                    result.Add([values[first], values[left], values[right]]);
                    int leftValue = values[left], rightValue = values[right];
                    while (left < right && values[left] == leftValue) left++;
                    while (left < right && values[right] == rightValue) right--;
                }
            }
        }
        return result.ToArray();
    }
}

复杂度： 排序 O(n log n)，双指针 O(n²)，额外空间取决于排序实现和结果。

边界用例： 少于三个元素；全部为零；重复值；整数和溢出。

面试追问：

• 四数之和可以如何推广，复杂度是多少？

解题思路： 容量由短板决定，因此每轮移动较短的一侧。

不变量： 移动长板无法突破当前短板限制，被跳过组合不会更优。

public static class AlgCode041Solution
{
    public static long Solve(int[] heights)
    {
        int left = 0, right = heights.Length - 1;
        long best = 0;
        while (left < right)
        {
            long area = (long)Math.Min(heights[left], heights[right]) *
                (right - left);
            best = Math.Max(best, area);
            if (heights[left] <= heights[right]) left++;
            else right--;
        }
        return best;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)，面积使用 long。

边界用例： 少于两个元素；全零；相等短板；面积超过 int。

面试追问：

• 为什么移动较高一侧无法证明排除候选？

解题思路： 快指针扫描，慢指针维护不重复有效前缀。

不变量： [0,write) 是已扫描元素去重后的升序结果。

public static class AlgCode042Solution
{
    public static int Solve(int[] numbers)
    {
        if (numbers.Length == 0) return 0;
        int write = 1;
        for (int read = 1; read < numbers.Length; read++)
        {
            if (numbers[read] != numbers[write - 1])
                numbers[write++] = numbers[read];
        }
        return write;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空数组；全部相同；没有重复。

面试追问：

• 如果每个值最多允许保留两次，写指针条件如何调整？

解题思路： 记录字符最近下标，重复位于当前窗口内时推进左边界。

不变量： 窗口 [left,right] 内没有重复字符，left 从不回退。

public static class AlgCode043Solution
{
    public static int Solve(string text)
    {
        var last = new Dictionary<char, int>();
        int left = 0, best = 0;
        for (int right = 0; right < text.Length; right++)
        {
            char value = text[right];
            if (last.TryGetValue(value, out int previous))
                left = Math.Max(left, previous + 1);
            last[value] = right;
            best = Math.Max(best, right - left + 1);
        }
        return best;
    }
}

复杂度： 时间 O(n)，额外空间 O(k)。

边界用例： 空字符串；全部相同；代理项按两个 char 处理。

面试追问：

• 如果按 Rune 计数，如何同时维护 UTF-16 下标？

解题思路： 右端扩张增加和，满足条件时持续移动左端并更新答案。

不变量： 收缩结束后当前窗口不满足目标，所有刚移除前的合法窗口已比较。

public static class AlgCode044Solution
{
    public static int Solve(int target, int[] numbers)
    {
        int left = 0, best = int.MaxValue;
        long sum = 0;
        for (int right = 0; right < numbers.Length; right++)
        {
            sum += numbers[right];
            while (sum >= target)
            {
                best = Math.Min(best, right - left + 1);
                sum -= numbers[left++];
            }
        }
        return best == int.MaxValue ? 0 : best;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 无解；单元素满足；总和使用 long；正数前提。

面试追问：

• 出现负数时可以使用前缀和加单调队列解决哪种变体？

解题思路： 维护需求频次和窗口频次；全部字符满足时持续收缩。

不变量： formed 表示当前窗口中已达到需求次数的不同字符数量。

public static class AlgCode045Solution
{
    public static string Solve(string source, string target)
    {
        if (target.Length == 0) return string.Empty;
        var need = new Dictionary<char, int>();
        foreach (char value in target)
            need[value] = need.GetValueOrDefault(value) + 1;
        var window = new Dictionary<char, int>();
        int formed = 0, left = 0, bestStart = 0, bestLength = int.MaxValue;
        for (int right = 0; right < source.Length; right++)
        {
            char added = source[right];
            window[added] = window.GetValueOrDefault(added) + 1;
            if (need.TryGetValue(added, out int required) &&
                window[added] == required) formed++;
            while (formed == need.Count)
            {
                if (right - left + 1 < bestLength)
                    (bestStart, bestLength) = (left, right - left + 1);
                char removed = source[left++];
                if (need.TryGetValue(removed, out required) &&
                    window[removed] == required) formed--;
                window[removed]--;
            }
        }
        return bestLength == int.MaxValue
            ? string.Empty
            : source.Substring(bestStart, bestLength);
    }
}

复杂度： 时间 O(n+m)，额外空间 O(k)。

边界用例： 目标为空；无解；重复需求字符；大小写不同。

面试追问：

• 如果字符集固定为 ASCII，怎样用数组降低哈希常数？

解题思路： 先求首个窗口和，随后每次加入右端并移除左端。

不变量： sum 始终等于当前长度为 k 的窗口元素和。

public static class AlgCode046Solution
{
    public static double Solve(int[] numbers, int k)
    {
        long sum = 0;
        for (int index = 0; index < k; index++) sum += numbers[index];
        long best = sum;
        for (int right = k; right < numbers.Length; right++)
        {
            sum += numbers[right] - numbers[right - k];
            best = Math.Max(best, sum);
        }
        return (double)best / k;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)，窗口和使用 long。

边界用例： k=1；k 等于数组长度；负数；和超过 int。

面试追问：

• 如果窗口长度不固定而要求平均值至少为阈值，问题会如何变化？