0996. Number of Squareful Arrays¶
题目信息¶
- 题号:
0996
- 难度:
Hard
- 主题:
数组排列、完全平方数、重复值去重
- 原题:
- 重点:
排列中每对相邻元素之和都必须是完全平方数;含重复值时只按最终数值序列区分排列,相同序列不重复计数
题目重述¶
给定整数数组 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] 合法。