ID: 468

Difficulty: 7

所属公司 : 科大讯飞

时间 :2023年8月13日

题目描述

小红有两个长度长度为 $n$ 的排列，并且想用计算机给他们存起来。

但小红的计算机存储算法很神奇，它只会存储排列的子排列，并且不会存储重复的排列。

思路：双指针

题目要我们求两个排列的本质不同的子排列(连续的)。

直接计算不好做，正难则反。先求所有可能。然后减去重复的就行。

长度为 $x$ 的所有子排列个数为 $x*(x+1)/2$ ，两个排列一共是 $x*(x+1)$

接下来的问题就是如何找出两个排列中重复的排列。