判断序列是否由两个相同子序列交错构成的算法求解求助

你的原有实现存在两个核心问题：

1. 数组越界风险：题目明确说明元素取值范围是1~1e5，但你只开了长度为10001的positions数组，一旦元素超过10000就会触发越界访问，导致未定义行为。
2. 逻辑缺陷：仅校验了元素出现次数为偶数，按奇偶位置分配元素到两个子序列的逻辑，没有保证两个子序列的相对顺序一致，会出现元素数量匹配但顺序不匹配的错误结果。比如测试用例[1,2,2,1]本身不可拆分，但原有代码会错误返回YES。

• 基础校验：如果n为奇数，直接返回NO；统计所有元素出现次数，只要有一个元素出现次数为奇数，直接返回NO。
• 贪心构造子序列：我们需要构造两个完全相同的子序列s和t，长度都为n/2。遍历原数组的每个元素：
  • 当s的长度还没到n/2时，如果当前t的长度等于s的长度，或者当前元素不等于s中t待匹配位置的元素，就将当前元素加入s。
  • 否则判断当前元素是否等于s中t待匹配位置的元素，如果是就加入t，否则直接返回NO。
• 遍历结束后如果s和t的长度都为n/2，说明构造成功，输出s即可。

该算法时间复杂度为O(n)，可以轻松处理n=5e4的上限要求。

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    if (n % 2 != 0) {
        cout << "NO\n";
        return 0;
    }
    int half = n / 2;
    vector<int> arr(n);
    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        cnt[arr[i]]++;
    }
    // 校验所有元素出现次数为偶数
    for (auto& p : cnt) {
        if (p.second % 2 != 0) {
            cout << "NO\n";
            return 0;
        }
    }

    vector<int> s, t;
    for (int x : arr) {
        if (s.size() < half && (t.size() == s.size() || x != s[t.size()])) {
            s.push_back(x);
        } else {
            if (t.size() < s.size() && x == s[t.size()]) {
                t.push_back(x);
            } else {
                cout << "NO\n";
                return 0;
            }
        }
    }

    if (s.size() == half && t.size() == half) {
        cout << "YES\n";
        for (int i = 0; i < s.size(); ++i) {
            if (i > 0) cout << " ";
            cout << s[i];
        }
        cout << "\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

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