You need to enable JavaScript to run this app. C# 查找和为N的幸运子序列前10项:同长度元素降序排序实现问题
优惠活动
大模型
产品
解决方案
定价
更多

C# 查找和为N的幸运子序列前10项:同长度元素降序排序实现问题

问题根源

你之前的实现偏差本质是对同长度排序规则的理解偏移:将“按子序列元素逐位降序比较”错等同于“按原数组中的起始索引先后排序”,而题目要求的同长度排序逻辑完全不涉及子序列在原数组的位置,只和子序列本身的元素内容有关。

正确实现方案

1. 定义Sequence类承载子序列,内置规则化比较逻辑

按照题目提示实现IComparable<Sequence>接口,把排序规则硬编码到比较方法中,完全避免外部排序逻辑的误用:

public class Sequence : IComparable<Sequence>
{
    // 直接存储子序列的元素引用,不存储冗余的原数组索引
    private readonly int[] _content;
    public int Length => _content.Length;

    public Sequence(int[] content)
    {
        _content = content;
    }

    public int CompareTo(Sequence? other)
    {
        if (other is null) return 1;
        
        // 第一优先级:子序列长度降序
        if (this.Length != other.Length)
        {
            // 长度更长的子序列排序优先级更高,排得更靠前
            return other.Length.CompareTo(this.Length);
        }

        // 第二优先级:同长度下从左到右逐元素降序比较
        for (int i = 0; i < this.Length; i++)
        {
            if (this._content[i] != other._content[i])
            {
                // 第一个不相等位置的元素值更大的子序列排前面
                return other._content[i].CompareTo(this._content[i]);
            }
        }

        // 所有元素完全相等时,两个子序列排序优先级一致
        return 0;
    }

    // 方便输出子序列内容的辅助方法
    public override string ToString() => $"[{string.Join(", ", _content)}]";
}

2. 同长度排序的核心判断逻辑说明

对两个等长的幸运子序列S1、S2,比较规则等价于反向字典序比较:

  • 从子序列的第一个元素开始逐位对比,找到第一个值不相等的位置
  • 该位置上元素值更大的子序列,整体排序更靠前
  • 整个比较过程完全不涉及子序列在原P数组中的起始位置、结束位置等元信息

举个对应测试用例的实际对比示例:
给定测试用例P = {1,1,2,1,-1,2,3,-1,1,2,3,5,1,-1,2,3},N=5,找到两个长度为4的幸运子序列:

  • S1 = [1,1,2,1](从原数组索引0开始)
  • S2 = [-1,1,2,3](从原数组索引7开始)

逐位比较时,第一个位置的1 > -1,因此S1排在S2前面,和S2在原数组中的位置无关。之前按起始索引升序排序的逻辑,会把位置更靠后的S2排到S1前面,和题目要求的规则完全相反,这就是结果偏差的核心来源。

3. 高性能Top10维护逻辑

按照题目提示,借助有序结构维护排序后的子序列,不需要存储所有幸运子序列再全量排序:

  • 每找到一个新的幸运子序列,就把它插入到有序集合中
  • 每次插入完成后,检查集合大小,如果超过10,直接移除集合中排序优先级最低的元素(也就是集合里排最末尾的那个)
  • 遍历完所有可能的连续子数组后,集合中保留的就是最终需要输出的前10项

这种方式的内存占用始终只和Top10的大小有关,不会因为幸运子序列过多导致内存溢出,适配L最大50000的输入规模。

避坑提醒
  • 不要额外存储原数组的起始索引作为同长度下的排序键,这是最常见的规则误解来源
  • 逐元素比较时必须严格从左到右(即从子序列的第一个元素开始对比),不能从右往左比、也不能替换成元素和、元素乘积等其他统计指标
  • 不要用ArrayList作为子序列的存储类型,其元素访问效率低于原生int数组,会增加逐位比较的耗时

内容的提问来源于stack exchange,提问作者Yo Yeah

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.29 19:27:07