求循环链表中长度至少为K的最小和最长连续子序列

从你给出的示例答案来看，目标应该是寻找长度至少为4的连续子序列中和最小的（示例子序列-33->-25->14->-12->-55的和为-111，是所有符合长度要求的子序列中最小的）。以下是O(n)时间复杂度的解法：

核心思路 #

循环链表的连续子序列分为两种情况：

1. 子序列是链表中的一段连续节点（不跨首尾）；
2. 子序列跨链表首尾（即从某节点到链表末尾，再从链表开头到某节点）。

我们先将循环链表转化为线性数组（O(n)时间），再分别处理两种情况，最后取最优解。

步骤1：循环链表转线性数组 #

遍历循环链表一次，将所有节点的值存入数组arr。示例数组为：[-12, -55, 47, -33, -25, 14]，长度n=6。

步骤2：计算数组总和 #

计算数组所有元素的总和total_sum，用于处理跨首尾的情况。示例中total_sum = -12 + (-55) + 47 + (-33) + (-25) + 14 = -64。

步骤3：处理非跨首尾的情况 #

我们需要找到长度≥4的最小和子数组，通过前缀和+维护最大前缀的方式实现：

• 计算前缀和数组prefix，其中prefix[0] = 0，prefix[i] = arr[0] + arr[1] + ... + arr[i-1]；
• 遍历i从4到n（对应子数组长度≥4），对于每个i，找到j ≤ i-4中最大的prefix[j]，此时prefix[i] - prefix[j]就是以arr[i-1]结尾的长度≥4的子数组最小和；
• 维护遍历过程中的最小值，即为非跨首尾情况的最优解。

示例中，非跨首尾的最小和为-66，对应子数组[-55, 47, -33, -25]。

步骤4：处理跨首尾的情况 #

跨首尾的子序列等价于数组总和减去中间一段长度≤n-4的子数组的和。要让跨首尾子序列的和最小，需要找到中间那段长度≤n-4的最大和子数组：

• 同样使用前缀和数组，遍历i从1到n，对于每个i，找到j ≥ i - (n-4)中最小的prefix[j]，此时prefix[i] - prefix[j]就是以arr[i-1]结尾的长度≤n-4的子数组最大和；
• 维护遍历过程中的最大和max_mid_sum，则跨首尾情况的最优和为total_sum - max_mid_sum。

示例中，n-4=2，即找长度≤2的最大和子数组（值为47），跨首尾的最优和为-64 - 47 = -111，对应子序列就是你给出的-33->-25->14->-12->-55。

步骤5：确定最终结果 #

比较两种情况的最优和，取较小值对应的子序列即可。

伪代码实现 #

def min_subsequence_circular(arr, k=4):
    n = len(arr)
    if n < k:
        return None  # 不符合长度要求
    
    total_sum = sum(arr)
    prefix = [0]*(n+1)
    for i in range(n):
        prefix[i+1] = prefix[i] + arr[i]
    
    # 处理非跨首尾情况：长度≥k的最小和
    min_linear = float('inf')
    max_prefix = prefix[0]
    for i in range(k, n+1):
        current_sum = prefix[i] - max_prefix
        if current_sum < min_linear:
            min_linear = current_sum
        # 更新最大前缀，包含当前prefix[i-k+1]
        if prefix[i - k + 1] > max_prefix:
            max_prefix = prefix[i - k + 1]
    
    # 处理跨首尾情况：等价于total_sum - 长度≤n-k的最大和子数组
    max_mid = float('-inf')
    min_prefix = prefix[0]
    m = n - k  # 中间子数组的最大长度
    for i in range(1, n+1):
        # 当i超过m时，需要移除超出范围的prefix[j]
        if i > m:
            if prefix[i - m - 1] < min_prefix:
                min_prefix = prefix[i - m -1]
        current_mid_sum = prefix[i] - min_prefix
        if current_mid_sum > max_mid:
            max_mid = current_mid_sum
    
    min_circular = total_sum - max_mid
    
    # 取最小值
    min_total = min(min_linear, min_circular)
    
    # 此处可添加逻辑，根据min_total找到对应的子序列节点（略）
    return min_total

复杂度分析 #

• 时间复杂度：O(n)，所有遍历操作均为线性时间；
• 空间复杂度：O(n)，用于存储前缀和数组。若优化前缀和计算（边遍历边计算），可将空间复杂度降至O(1)。

内容的提问来源于stack exchange，提问作者smulslippy