Medium

题目描述

给你一个整数数组 nums。

使用以下规则将 nums 分割成两个数组 A 和 B：

  • nums 中质数索引处的元素必须放入数组 A。
  • 所有其他元素必须放入数组 B。

返回两个数组和的绝对差值：|sum(A) - sum(B)|。

注意：空数组的和为 0。

示例 1：

输入：nums = [2,3,4]
输出：1
解释：
数组中唯一的质数索引是 2，所以 nums[2] = 4 被放入数组 A。
剩余的元素 nums[0] = 2 和 nums[1] = 3 被放入数组 B。
sum(A) = 4，sum(B) = 2 + 3 = 5。
绝对差值为 |4 - 5| = 1。

示例 2：

输入：nums = [-1,5,7,0]
输出：3
解释：
数组中的质数索引是 2 和 3，所以 nums[2] = 7 和 nums[3] = 0 被放入数组 A。
剩余的元素 nums[0] = -1 和 nums[1] = 5 被放入数组 B。
sum(A) = 7 + 0 = 7，sum(B) = -1 + 5 = 4。
绝对差值为 |7 - 4| = 3。

约束：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

解题思路

这道题需要我们：

  1. 识别出哪些索引是质数
  2. 将质数索引处的元素归入数组A，其余元素归入数组B
  3. 计算两个数组和的绝对差值

核心步骤：

  1. 生成质数表：使用埃拉托色尼筛法预处理出所有小于等于数组长度的质数。这是最高效的方法，时间复杂度为 O(n log log n)。

  2. 分类求和：遍历数组，根据索引是否为质数将元素分别累加到 sumA 和 sumB 中。

  3. 计算绝对差值：返回 |sumA - sumB|。

算法优化：

  • 由于数组元素可能很大（±10^9），需要使用长整型避免溢出
  • 埃拉托色尼筛法的空间复杂度为 O(n)，但对于n≤10^5完全可以接受
  • 也可以考虑直接判断质数的方法，但对于需要多次查询的场景，预处理更高效

推荐解法： 埃拉托色尼筛法 + 一次遍历求和，时间复杂度最优。

代码实现

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int n = nums.size();
        
        // 使用埃拉托色尼筛法生成质数
        vector<bool> isPrime(n, true);
        if (n > 0) isPrime[0] = false;
        if (n > 1) isPrime[1] = false;
        
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        long long sumA = 0, sumB = 0;
        for (int i = 0; i < n; i++) {
            if (isPrime[i]) {
                sumA += nums[i];
            } else {
                sumB += nums[i];
            }
        }
        
        return abs(sumA - sumB);
    }
};

class Solution:
    def splitArray(self, nums: List[int]) -> int:
        n = len(nums)
        
        # 使用埃拉托色尼筛法生成质数
        is_prime = [True] * n
        if n > 0:
            is_prime[0] = False
        if n > 1:
            is_prime[1] = False
        
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                for j in range(i * i, n, i):
                    is_prime[j] = False
        
        sum_a = sum_b = 0
        for i in range(n):
            if is_prime[i]:
                sum_a += nums[i]
            else:
                sum_b += nums[i]
        
        return abs(sum_a - sum_b)

public class Solution {
    public long SplitArray(int[] nums) {
        int n = nums.Length;
        
        // 使用埃拉托色尼筛法生成质数
        bool[] isPrime = new bool[n];
        Array.Fill(isPrime, true);
        if (n > 0) isPrime[0] = false;
        if (n > 1) isPrime[1] = false;
        
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        long sumA = 0, sumB = 0;
        for (int i = 0; i < n; i++) {
            if (isPrime[i]) {
                sumA += nums[i];
            } else {
                sumB += nums[i];
            }
        }
        
        return Math.Abs(sumA - sumB);
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var splitArray = function(nums) {
    const n = nums.length;
    
    // 使用埃拉托色尼筛法生成质数
    const isPrime = new Array(n).fill(true);
    if (n > 0) isPrime[0] = false;
    if (n > 1) isPrime[1] = false;
    
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let sumA = 0, sumB = 0;
    for (let i = 0; i < n; i++) {
        if (isPrime[i]) {
            sumA += nums[i];
        } else {
            sumB += nums[i];
        }
    }
    
    return Math.abs(sumA - sumB);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n log log n + n) = O(n log log n)
空间复杂度O(n)

其中 n 为数组长度。时间复杂度主要来自埃拉托色尼筛法生成质数表，空间复杂度来自存储质数标记数组。