解题思路
从左向右找到第一个 pi=qi 的位置 l,从右向左找到最后一个不相等的位置 r。若整段都相等,则 l=r=0,对应把长度为 1 的区间翻转(序列不变),答案为 1。
否则,检查把 p[l..r] 翻转后是否恰好等于 q[l..r]:用两个指针同时从两端向中间走,判断 p[left] 是否等于 q[right]。只要有一处对不上,说明这一段不是另一段的逆序,答案为 0。
若这一段翻转后已经对齐,则这一组 [l,r] 是一种合法选择。还可以尝试把区间同时向两边扩张:当 l−1≥0、r+1<n 且 pl−1=pr+1 时,扩张后翻转仍然合法(外侧本来就已经与 q 相等)。每成功扩张一次,答案加 1。
复杂度分析