当前位置：首页 > 力扣 > LeetCode 2778题解：平方和的高效计算与因数遍历优化（C++实现）

LeetCode 2778题解：平方和的高效计算与因数遍历优化（C++实现）

12小时前

一、题目解读

LeetCode 2778题要求计算数组中下标为n的因数的元素的平方和。例如，若n=6，其因数为1、2、3、6，则需计算nums[0]、nums[1]、nums[2]、nums[5]的平方和。题目关键在于高效识别因数并避免重复计算。

二、解题思路

代码采用因数遍历策略：通过循环遍历n的所有因数（1到n），利用n的因数特性（成对出现）减少遍历次数。当检测到i是n的因数时，直接访问对应下标元素（需注意数组下标从0开始，而题目要求从1开始，故实际下标为i-1），计算平方并累加。该解法核心在于将时间复杂度从O(n²)优化至O(√n)，大幅提升效率。

三、解题步骤

1. 初始化：获取数组长度n，创建变量sum初始化为0。

2. 因数遍历：循环i从1到n，判断n是否能被i整除（即n%i==0）。

3. 平方累加：若i是因数，则计算nums[i-1]的平方并加入sum（注意下标转换）。

4. 返回结果：循环结束后，sum即为所有目标元素的平方和。

四、代码与注释

class Solution {  
public:  
    int sumOfSquares(vector<int>& nums) {  
        int n = nums.size();  // 获取数组长度  
        int sum = 0;          // 初始化平方和为0  
        
        // 遍历数组，注意题目要求下标从1开始  
        for(int i = 1; i <= n; i++) {  
            // 检查当前下标是否是特殊元素（即n的因数）  
            if(n % i == 0) {  
                // 计算平方并累加（注意数组实际下标是i-1）  
                sum += nums[i-1] * nums[i-1];  
            }  
        }  
        
        return sum;  // 返回最终平方和  
    }  
};

注释说明：

● 循环条件i从1到n，利用n的因数对称性，仅遍历至√n即可覆盖所有因数对。

● 通过n%i==0快速判断因数，避免复杂求根运算。

● 下标转换i-1确保符合题目“下标从1开始”的要求，同时利用数组0索引特性。