计算由不同元素子数组形成的对数（Java）

给定一个数组，我们的任务是找出可以从每个包含不同整数的潜在连续子数组中形成多少对。数组中的正数范围从 0 到 n-1，其中 n 是数组的大小。

示例 1

输入

int a[] = [4, 8, 8, 9]

输出

子数组元素形成的不同的对总数为 2。

解释

对于给定的数组 [4, 8, 8, 9]，可以形成的子数组有 (4,8) 和 (8,9) 这两对不同的元素。因此，不同的对总数为 2。

示例 2

输入

int a[] = [1, 4, 2, 4, 3, 2]

输出

子数组元素形成的不同的对总数为 8。

解释

对于给定的数组 [1, 4, 2, 4, 3, 2]，可以形成的子数组是 [1, 4, 2]、[2, 4, 3] 和 [4, 3, 2]。因此，从这些子数组中，我们可以轻松地形成不同的对，如 (1, 4)、(1, 2)、(4, 2)、(2, 4)、(2, 3)、(4, 3)、(4, 2)、(3, 2)。因此，不同的对总数为 8。

方法：滑动窗口

在给定方法中，可以使用滑动窗口技术来跨越给定数组的连续子数组维护一个窗口。这个想法是利用滑动窗口来处理指定的数组。其主要目标是确保滑动窗口中的每个元素都是唯一的。为了标记当前窗口中的元素，让我们使用一个从索引 left 到索引 right 的窗口覆盖和一个布尔数组 visited。原则是窗口内的每个元素都是唯一的，并且窗口是连续的。直到所有元素再次唯一，我们继续将窗口向右扩展。如果发现重复项，则从左侧缩小窗口。

随着我们进行，我们更新当前窗口中的对数。一项特定结果表明，一个不断扩展的窗口中的对数可以按因子一或窗口大小减一进行增加。索引 left 是窗口的开始位置，索引 right 是窗口的结束位置。

实施

文件名： CountPairsFromSubarrays.java

输出

The total number of distinct pairs formed by the elements of sub-arrays is 8

复杂度分析

时间复杂度为 O(N^2)，其中 'N' 表示给定数组的大小。空间复杂度为 O(N)，因为使用 visited 数组来标记当前窗口的元素。