Easy

题目描述

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

对于数组 nums 中的元素 nums[i]，如果 i 能整除 n，即 n % i == 0，则认为 nums[i] 是一个 特殊元素。

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

示例 1：

输入：nums = [1,2,3,4]
输出：21
解释：nums 中共有 3 个特殊元素：nums[1]，因为 1 整除 4；nums[2]，因为 2 整除 4；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]，因为 1 整除 6；nums[2]，因为 2 整除 6；nums[3]，因为 3 整除 6；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

解题思路

这是一道简单的数组遍历题目。关键是理解题意：

  • 数组是 1-indexed（从索引 1 开始）
  • 特殊元素的定义是：索引 i 能整除数组长度 n

解题思路：

由于题目给出的数组是 1-indexed，但实际编程中数组通常是 0-indexed，我们需要注意索引的转换。对于 0-indexed 数组中索引为 i 的元素，它在 1-indexed 中的位置是 i+1。

因此，我们需要检查 (i+1) 是否能整除 n，即 n % (i+1) == 0。

算法步骤：

  1. 遍历数组的每个索引 i（0 到 n-1）
  2. 检查 (i+1) 是否能整除 n
  3. 如果能整除，则 nums[i] 是特殊元素，将其平方加入结果
  4. 返回所有特殊元素平方的总和

这种方法简单直接，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int sumOfSquares(vector<int>& nums) {
        int n = nums.size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            if (n % (i + 1) == 0) {
                result += nums[i] * nums[i];
            }
        }
        
        return result;
    }
};

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

public class Solution {
    public int SumOfSquares(int[] nums) {
        int n = nums.Length;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            if (n % (i + 1) == 0) {
                result += nums[i] * nums[i];
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfSquares = function(nums) {
    let sum = 0;
    const n = nums.length;
    
    for (let i = 1; i <= n; i++) {
        if (n % i === 0) {
            sum += nums[i - 1] * nums[i - 1];
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个数组一次
空间复杂度O(1)只使用了常数个额外变量

相关题目