特殊元素平方和

标签: 数组 枚举

难度: Easy

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个 特殊元素 。

返回 nums 中所有 特殊元素 的 平方和 。

示例 1：

输入：nums = [1,2,3,4]
输出：21
解释：nums 中共有 3 个特殊元素：nums[1]，因为 4 被 1 整除；nums[2]，因为 4 被 2 整除；以及 nums[4]，因为 4 被 4 整除。 
因此，nums 中所有特殊元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[4] * nums[4] = 1 * 1 + 2 * 2 + 4 * 4 = 21 。

示例 2：

输入：nums = [2,7,1,19,18,3]
输出：63
解释：nums 中共有 4 个特殊元素：nums[1]，因为 6 被 1 整除；nums[2] ，因为 6 被 2 整除；nums[3]，因为 6 被 3 整除；以及 nums[6]，因为 6 被 6 整除。 
因此，nums 中所有特殊元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63 。

提示：

  • 1 <= nums.length == n <= 50
  • 1 <= nums[i] <= 50

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        sum = 0
        for i in range(len(nums)):
            if len(nums) % (i+1) == 0:
                sum += nums[i]*nums[i]
        return sum

Explain

题解通过遍历数组 `nums` 来检查每个下标 `i`（从 0 开始）是否满足 `n % (i+1) == 0` 的条件。这里的 `i+1` 表示从 1 开始的下标。如果满足条件，说明 `nums[i]` 是特殊元素，将其平方后加入到累加器 `sum` 中。循环结束后返回 `sum`，即所有特殊元素平方和。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        sum = 0  # 初始化平方和变量
        for i in range(len(nums)):
            if len(nums) % (i+1) == 0:  # 检查 n 是否能被下标 i+1 整除
                sum += nums[i]*nums[i]  # 累加特殊元素的平方
        return sum  # 返回所有特殊元素的平方和

Explore

在算法中使用 i+1 作为除数进行整除检查是因为数组的下标从 0 开始，但在数学和逻辑运算中，通常从 1 开始进行计数更为自然。因此，使用 i+1 是为了将数组下标转换为自然数序列（1, 2, 3, ...），以便正确地检查数组长度是否能够被这些自然数整除。如果使用 i 作为除数，由于数组下标从 0 开始，将会导致第一个元素用 0 作为除数，这在数学上是没有意义并且会导致运行时错误。

如果数组中的元素值非常大，平方这些数值可能会导致数值超过程序中整数类型的最大表达范围，这被称为整数溢出。在 Python 中，整数类型会自动转换为长整形以适应大数值，因此通常不会遇到溢出错误。但在其他一些编程语言中，如 C++ 或 Java，整数类型有固定大小，超过这个大小的数值会导致溢出错误，这可能会导致结果不准确或程序崩溃。因此，编写算法时需要考虑这一点，可能需要使用特殊的数据类型或方法来处理大数值的情况。

在这个算法中，使用 len(nums) 作为被除数，这里假定 len(nums) 实际上就是题目中提到的 n，即数组 nums 的长度。通常情况下，n 被用来表示数组的长度，因此这里直接使用 len(nums) 作为 n 是合理的。这意味着我们假设数组的长度就是题目中提到的 n，而无需额外的变量来专门存储这个值。

在目前的算法实现中，如果 nums 数组为空，代码中的 for 循环体将不会执行，因为 range(len(nums)) 会返回一个空范围。因此，sum 变量将保持其初始值 0，并将其作为结果返回。这种处理方式正确处理了数组为空的边界情况，因为没有元素意味着没有特殊元素，所以平方和应该是 0。