0996. Number of Squareful Arrays

题目信息

题号:

0996

难度:

Hard

主题:

数组排列、完全平方数、重复值去重

原题:

LeetCode 0996

重点:

排列中每对相邻元素之和都必须是完全平方数;含重复值时只按最终数值序列区分排列,相同序列不重复计数

题目重述

给定整数数组 nums。重新排列数组中的全部元素,若排列中每一对相邻元素的和都是某个非负整数的平方,则称该排列为平方数组。

请返回内容互不相同的平方排列数量。数组可能包含重复值;交换两个相等元素不会产生新的数值序列,因此不能重复计数。只有在某个位置上的值不同,两个排列才算不同。

1 <= nums.length <= 12,0 <= nums[i] <= 10^9。

自建示例

两个相等元素形成三种不同排列:

输入:nums = [1,8,8]
输出:3
解释:[1,8,8]、[8,1,8] 和 [8,8,1] 均满足相邻和为 9 或 16。两个 8 互换不会形成新的数值序列。

数组只有一个元素:

输入:nums = [7]
输出:1
解释:单元素排列没有相邻元素对需要检查,因此唯一排列 [7] 合法。