日期: 2026年5月8日

目标

给你一个长度为 n 的整数数组 nums。

你从下标 0 开始，目标是到达下标 n - 1。

在任何下标 i 处，你可以执行以下操作之一：

• 移动到相邻格子：跳到下标 i + 1 或 i - 1，如果该下标在边界内。
• 质数传送：如果 nums[i] 是一个质数 p，你可以立即跳到任何满足 nums[j] % p == 0 的下标 j 处，且下标 j != i 。

返回到达下标 n - 1 所需的 最少 跳跃次数。

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

示例 1:

输入: nums = [1,2,4,6]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 1 跳一步。
在下标 i = 1，nums[1] = 2 是一个质数。因此，我们传送到索引 i = 3，因为 nums[3] = 6 可以被 2 整除。
因此，答案是 2。

示例 2:

输入: nums = [2,3,4,7,9]
输出: 2
解释:
一个最优的跳跃序列是：
从下标 i = 0 开始。向相邻下标 i = 1 跳一步。
在下标 i = 1，nums[1] = 3 是一个质数。因此，我们传送到下标 i = 4，因为 nums[4] = 9 可以被 3 整除。
因此，答案是 2。

示例 3:

输入: nums = [4,6,5,8]
输出: 3
解释:
由于无法进行传送，我们通过 0 → 1 → 2 → 3 移动。因此，答案是 3。

说明:

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 10^6

思路

有一个数组 nums，从下标 0 开始移动，目标是到达下标 n - 1。每次移动可以移动到相邻的位置，如果 nums[i] 是质数，可以直接移动到满足 nums[j] % nums[i] == 0 的位置。返回最少移动次数。

枚举 2 ~ MAX，为每一个数记录质因子，得到哈希表 (num，primeFactorList)，枚举数组中的元素，获取 primeFactorList，为其中的每一个质数建立一个跳转列表 jumpIndexList，将当前下标加进去。从 0 开始 bfs，记录跳转次数，直到到达下标 n - 1。

代码

/**
 * @date 2026-05-08 16:55
 */
public class MinJumps3629 {

    public static final int MAX = 1000000;
    public static Map<Integer, List<Integer>> primeFactorMap = new HashMap<>();

    static {
        primeFactorMap.computeIfAbsent(1, k -> new ArrayList<>());
        for (int i = 2; i <= MAX; i++) {
            if (primeFactorMap.get(i) == null) {
                for (int j = i; j <= MAX; j += i) {
                    primeFactorMap.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
                }
            }
        }
    }

    public int minJumps(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> jumpIndexList = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> primeFactors = primeFactorMap.get(nums[i]);
            for (Integer prime : primeFactors) {
                jumpIndexList.computeIfAbsent(prime, k -> new ArrayList<>()).add(i);
            }
        }
        boolean[] visited = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(0);
        int res = 0;
        here:
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Integer index = q.poll();
                if (visited[index]) {
                    continue;
                }
                visited[index] = true;
                if (index == n - 1) {
                    break here;
                }
                int next = index + 1;
                int prev = index - 1;
                if (next < n) {
                    q.offer(next);
                }
                if (prev >= 0) {
                    q.offer(prev);
                }
                if (jumpIndexList.get(nums[index]) != null) {
                    q.addAll(jumpIndexList.get(nums[index]));
                    jumpIndexList.get(nums[index]).clear();
                }
            }
            res++;
        }
        return res;
    }

}

性能