C++ 实现 Python 代码：滑动窗口排序优化

#include #include #include <unordered_map> #include

using namespace std;

tuple<int, int, int> get_ans(vector nums, unordered_map<int, int> dic, int right, int k) { int x = 0, first = 0, second = 0;

if (dic.size() == 1) {
    first = dic.begin()->second;

    int num_miss = (1 + k) * k / 2 - accumulate(nums.begin() + right - k + 1, nums.begin() + right + 1, 0) + dic.begin()->first;

    second = find(nums.begin(), nums.end(), num_miss) - nums.begin();

    if (second == right + 1 && first == right - k + 1) {
        x = 0;
    } else {
        x = 1;
    }
}

return make_tuple(x, first, second);

}

int main() { int n, k; cin >> n >> k;

vector<int> nums(n);
for (int i = 0; i < n; i++) {
    cin >> nums[i];
}

int x = 2;
unordered_map<int, int> dic;
for (int i = 0; i < k; i++) {
    if (nums[i] > k) {
        dic[nums[i]] = i;
    }
}

if (dic.size() <= 1) {
    int first, second;
    tie(x, first, second) = get_ans(nums, dic, k - 1, k);
} else {
    for (int right = k; right < n; right++) {
        if (nums[right] > k) {
            dic[nums[right]] = right;
        }

        int left = right - k;
        int left_num = nums[left];

        if (left_num > k) {
            dic.erase(left_num);
        }

        if (dic.size() <= 1) {
            int first, second;
            tie(x, first, second) = get_ans(nums, dic, right, k);
            break;
        }
    }
}

if (x <= 1) {
    cout << "YES" << endl;
    if (x == 1) {
        cout << 1 << endl;
        if (first > second) {
            swap(first, second);
        }
        cout << first << " " << second << endl;
    } else {
        cout << 0 << endl;
    }
} else {
    cout << "NO" << endl;
}

return 0;

}