What is the main challenge in Split Array by Prime Indices?

The key challenge is correctly identifying prime indices and efficiently computing the absolute difference of sums without iterating redundantly.

Can negative numbers in nums affect the result?

Yes, negative values impact the sums directly, so the solution must account for both positive and negative numbers accurately.

Is using a Sieve of Eratosthenes necessary?

Using a sieve is the most efficient way to identify all prime indices up to nums.length, avoiding repeated primality checks.

Does the algorithm work for arrays of length 1 or 2?

Yes, edge cases with very small arrays are handled by the prime index check, where only valid primes contribute to one array.

How does this problem relate to Array plus Math pattern?

It combines array iteration with number theory by using prime index logic and arithmetic operations to compute the absolute difference.

#3618

Medium

auto_awesome数组·数学

LeetCode 题解工作台

根据质数下标分割数组

给你一个整数数组 nums 。根据以下规则将 nums 分割成两个数组 A 和 B ： nums 中位于质数下标的元素必须放入数组 A 。所有其他元素必须放入数组 B 。返回两个数组和的绝对差值： |sum(A) - sum(B)| 。质数是一个大于 1 的自然数，它只有两个因子，…

数组数学数论

题目描述

给你一个整数数组 nums。

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

nums 中位于质数下标的元素必须放入数组 A。
所有其他元素必须放入数组 B。

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

质数是一个大于 1 的自然数，它只有两个因子，1和它本身。

注意：空数组的和为 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⁵
-10⁹ <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：埃氏筛 + 模拟

我们可以用埃氏筛法预处理出 $[0, 10^5]$ 范围内的所有质数。然后遍历数组 $\textit{nums}$ ，对于 $\textit{nums}[i]$ ，如果 $i$ 是质数，则将 $\textit{nums}[i]$ 加到答案中，否则将 $-\textit{nums}[i]$ 加到答案中。最后返回答案的绝对值。

忽略预处理的时间和空间，时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

m = 10**5 + 10
primes = [True] * m
primes[0] = primes[1] = False
for i in range(2, m):
    if primes[i]:
        for j in range(i + i, m, i):
            primes[j] = False


class Solution:
    def splitArray(self, nums: List[int]) -> int:
        return abs(sum(x if primes[i] else -x for i, x in enumerate(nums)))

speed

复杂度分析

指标	值
时间	complexity is O(n log log n) for the sieve plus O(n) for iterating the array, totaling O(n log log n). Space complexity is O(n) for the prime index mask, but the algorithm can reduce auxiliary storage by summing on the fly.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if you can optimize by avoiding repeated prime checks per index.
question_mark
Be ready to handle negative and large values while calculating sums.
question_mark
Consider edge cases where nums.length is very small or consists entirely of primes.

warning

常见陷阱

外企场景

error
Confusing array indices with element values when separating by prime indices.
error
Failing to account for the first index being 0 or 1, which are not prime.
error
Using inefficient prime checks instead of a sieve, leading to timeouts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Split array using odd or even indices instead of prime indices for a simpler variant.
arrow_right_alt
Compute maximum absolute difference rather than minimum, testing sum strategy changes.
arrow_right_alt
Use a sliding window of prime indices to handle dynamic array updates efficiently.

help

常见问题

外企场景

继续练习

#3605 数组的最小稳定性因子 #3591 检查元素频次是否为质数 #3589 计数质数间隔平衡子数组