❌

普通视图

发现新文章，点击刷新页面。
今天 — 2025年12月9日首页

两种方法：枚举中间 / 一次遍历（Python/Java/C++/Go）

✇LeetCode 每日一题题解
作者 endlesscheng
2025年6月15日 12:07

方法一：枚举中间

三变量问题，一般枚举中间的变量最简单。为什么？对比一下：

  • 枚举 $i$，后续计算中还需保证 $j < k$。
  • 枚举 $j$，那么 $i$ 和 $k$ 自动被 $j$ 隔开，互相独立，后续计算中无需关心 $i$ 和 $k$ 的位置关系。

枚举中间的 $j$，问题变成：

  • 在 $[0,j-1]$ 中，$\textit{nums}[j]\cdot 2$ 的出现次数。
  • 在 $[j+1,n-1]$ 中，$\textit{nums}[j]\cdot 2$ 的出现次数。
  • 在这些出现次数中，左右两边各选一个。根据乘法原理，把这两个出现次数相乘，加到答案中。

用哈希表（或者数组）统计 $j$ 左右每个数的出现次数。

  • 右边的元素出现次数，可以先统计整个数组，然后再次遍历数组，撤销 $[0,j]$ 中统计的元素出现次数，即为 $[j+1,n-1]$ 中的元素出现次数。
  • 左边的元素出现次数，可以一边遍历 $\textit{nums}$，一边统计。

由于答案不超过 $n\cdot 10^5\cdot 10^5 \le 10^{15}$，可以只在返回时取模。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        MOD = 1_000_000_007
        suf = Counter(nums)

        ans = 0
        pre = defaultdict(int)  # 比 Counter 快
        for x in nums:  # x = nums[j]
            suf[x] -= 1  # 撤销
            # 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
            ans += pre[x * 2] * suf[x * 2]
            pre[x] += 1
        return ans % MOD

###java

// 更快的写法见【Java 数组】
class Solution {
    public int specialTriplets(int[] nums) {
        final int MOD = 1_000_000_007;
        Map<Integer, Integer> suf = new HashMap<>();
        for (int x : nums) {
            suf.merge(x, 1, Integer::sum); // suf[x]++
        }

        long ans = 0;
        Map<Integer, Integer> pre = new HashMap<>();
        for (int x : nums) { // x = nums[j]
            suf.merge(x, -1, Integer::sum); // suf[x]-- // 撤销
            // 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
            ans += (long) pre.getOrDefault(x * 2, 0) * suf.getOrDefault(x * 2, 0);
            pre.merge(x, 1, Integer::sum); // pre[x]++
        }
        return (int) (ans % MOD);
    }
}

###java

class Solution {
    public int specialTriplets(int[] nums) {
        final int MOD = 1_000_000_007;
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }

        int[] suf = new int[mx + 1];
        for (int x : nums) {
            suf[x]++;
        }

        long ans = 0;
        int[] pre = new int[mx + 1];
        for (int x : nums) {
            suf[x]--;
            if (x * 2 <= mx) {
                ans += (long) pre[x * 2] * suf[x * 2];
            }
            pre[x]++;
        }
        return (int) (ans % MOD);
    }
}

###cpp

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int MOD = 1'000'000'007;
        unordered_map<int, int> suf;
        for (int x : nums) {
            suf[x]++;
        }

        long long ans = 0;
        unordered_map<int, int> pre;
        for (int x : nums) { // x = nums[j]
            suf[x]--; // 撤销
            // 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
            ans += 1LL * pre[x * 2] * suf[x * 2];
            pre[x]++;
        }
        return ans % MOD;
    }
};

###go

func specialTriplets(nums []int) (ans int) {
const mod = 1_000_000_007
suf := map[int]int{}
for _, x := range nums {
suf[x]++
}

pre := map[int]int{}
for _, x := range nums { // x = nums[j]
suf[x]-- // 撤销
// 现在 pre 中的是 [0,j-1]，suf 中的是 [j+1,n-1]
ans += pre[x*2] * suf[x*2]
pre[x]++
}
return ans % mod
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(n)$。

方法二：枚举右，维护左（一次遍历）

枚举 $k$，设 $x=\textit{nums}[k]$，问题变成：

  • 有多少个二元组 $(i,j)$，满足 $i<j<k$ 且 $\textit{nums}[i]=x$ 且 $\textit{nums}[j] = \dfrac{x}{2}$。用哈希表 $\textit{cnt}_{12}$ 记录这样的二元组个数。

这个问题也可以枚举右维护左，即枚举 $j$，问题变成：

  • 在 $j$ 左边有多少个数等于 $\textit{nums}[j]\cdot 2$？用哈希表 $\textit{cnt}_{1}$ 记录。

###py

class Solution:
    def specialTriplets(self, nums: List[int]) -> int:
        MOD = 1_000_000_007
        cnt1 = defaultdict(int)
        cnt12 = defaultdict(int)
        cnt123 = 0
        for x in nums:
            if x % 2 == 0:
                cnt123 += cnt12[x // 2]  # 把 x 当作 nums[k]
            cnt12[x] += cnt1[x * 2]  # 把 x 当作 nums[j]
            cnt1[x] += 1  # 把 x 当作 nums[i]
        return cnt123 % MOD

###java

class Solution {
    public int specialTriplets(int[] nums) {
        final int MOD = 1_000_000_007;
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Long> cnt12 = new HashMap<>();
        long cnt123 = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                cnt123 += cnt12.getOrDefault(x / 2, 0L); // 把 x 当作 nums[k]
            }
            cnt12.merge(x, (long) cnt1.getOrDefault(x * 2, 0), Long::sum); // 把 x 当作 nums[j]
            cnt1.merge(x, 1, Integer::sum); // 把 x 当作 nums[i]
        }
        return (int) (cnt123 % MOD);
    }
}

###cpp

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int MOD = 1'000'000'007;
        unordered_map<int, int> cnt1;
        unordered_map<int, long long> cnt12;
        long long cnt123 = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                cnt123 += cnt12[x / 2]; // 把 x 当作 nums[k]
            }
            cnt12[x] += cnt1[x * 2]; // 把 x 当作 nums[j]
            cnt1[x]++; // 把 x 当作 nums[i]
        }
        return cnt123 % MOD;
    }
};

###go

func specialTriplets(nums []int) (cnt123 int) {
const mod = 1_000_000_007
cnt1 := map[int]int{}
cnt12 := map[int]int{}
for _, x := range nums {
if x%2 == 0 {
cnt123 += cnt12[x/2] // 把 x 当作 nums[k]
}
cnt12[x] += cnt1[x*2] // 把 x 当作 nums[j]
cnt1[x]++ // 把 x 当作 nums[i]
}
return cnt123 % mod
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
  • 空间复杂度：$\mathcal{O}(n)$。

相似题目

更多相似题目，见下面数据结构题单的「§0.2 枚举中间」和动态规划题单的「专题：前后缀分解」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

昨天以前首页

划分型 DP + 单调队列优化（Python/Java/C++/Go）

✇LeetCode 每日一题题解
作者 endlesscheng
2025年6月8日 12:15

O(n^2) 做法

本题是标准的划分型 DP，见 DP 题单 的「§5.2 最优划分」。

一般定义 $f[i+1]$ 表示前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 在题目约束下，分割出的最少（最多）子数组个数，本题是定义成分割方案数。这里 $i+1$ 是为了把 $f[0]$ 当作初始值。

枚举最后一个子数组的左端点 $j$，那么问题变成前缀 $\textit{nums}[0]$ 到 $\textit{nums}[j-1]$ 在题目约束下的分割方案数，即 $f[j]$。

当子数组右端点 $i$ 固定时，由于子数组越长，最大值越大，最小值越小，最大最小的差值越可能大于 $k$。所以符合要求的左端点 $j$ 一定在一个连续区间 $[L,i]$ 中。累加 $f[j]$ 得

$$
f[i+1] = \sum_{j=L}^{i} f[j]
$$

初始值 $f[0] = 1$，空子数组算一个方案。也可以从递归的角度理解，递归到空子数组，就表示我们找到了一个合法分割方案。

答案为 $f[n]$。

O(n) 做法

由于 $i$ 越大，$L$ 也越大，可以用 滑动窗口【基础算法精讲 03】。

同时，我们需要计算 239. 滑动窗口最大值 和滑动窗口最小值，这可以用 单调队列【基础算法精讲 27】解决。

维护窗口中的 $\displaystyle\sum_{j=L}^{i} f[j]$，记作 $\textit{sumF}$，转移方程优化成

$$
f[i+1] = \textit{sumF}
$$

注意取模。关于模运算的知识点，见 模运算的世界：当加减乘除遇上取模。

本题视频讲解，欢迎点赞关注~

###py

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        MOD = 1_000_000_007
        n = len(nums)
        min_q = deque()
        max_q = deque()
        f = [0] * (n + 1)
        f[0] = 1
        sum_f = 0  # 窗口中的 f[i] 之和
        left = 0

        for i, x in enumerate(nums):
            # 1. 入
            sum_f += f[i]

            while min_q and x <= nums[min_q[-1]]:
                min_q.pop()
            min_q.append(i)

            while max_q and x >= nums[max_q[-1]]:
                max_q.pop()
            max_q.append(i)

            # 2. 出
            while nums[max_q[0]] - nums[min_q[0]] > k:
                sum_f -= f[left]
                left += 1
                if min_q[0] < left:
                    min_q.popleft()
                if max_q[0] < left:
                    max_q.popleft()

            # 3. 更新答案
            f[i + 1] = sum_f % MOD

        return f[n]

###java

class Solution {
    public int countPartitions(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        Deque<Integer> minQ = new ArrayDeque<>(); // 更快的写法见【Java 数组】
        Deque<Integer> maxQ = new ArrayDeque<>();
        int[] f = new int[n + 1];
        f[0] = 1;
        long sumF = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            // 1. 入
            sumF += f[i];

            int x = nums[i];
            while (!minQ.isEmpty() && x <= nums[minQ.peekLast()]) {
                minQ.pollLast();
            }
            minQ.addLast(i);

            while (!maxQ.isEmpty() && x >= nums[maxQ.peekLast()]) {
                maxQ.pollLast();
            }
            maxQ.addLast(i);

            // 2. 出
            while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > k) {
                sumF -= f[left];
                left++;
                if (minQ.peekFirst() < left) {
                    minQ.pollFirst();
                }
                if (maxQ.peekFirst() < left) {
                    maxQ.pollFirst();
                }
            }

            // 3. 更新答案
            f[i + 1] = (int) (sumF % MOD);
        }

        return f[n];
    }
}

###java

class Solution {
    public int countPartitions(int[] nums, int k) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        int[] minQ = new int[n];
        int[] maxQ = new int[n];
        int minHead = 0, minTail = -1;
        int maxHead = 0, maxTail = -1;
        int[] f = new int[n + 1];
        f[0] = 1;
        long sumF = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            // 1. 入
            sumF += f[i];

            int x = nums[i];
            while (minHead <= minTail && x <= nums[minQ[minTail]]) {
                minTail--;
            }
            minQ[++minTail] = i;

            while (maxHead <= maxTail && x >= nums[maxQ[maxTail]]) {
                maxTail--;
            }
            maxQ[++maxTail] = i;

            // 2. 出
            while (nums[maxQ[maxHead]] - nums[minQ[minHead]] > k) {
                sumF -= f[left];
                left++;
                if (minQ[minHead] < left) {
                    minHead++;
                }
                if (maxQ[maxHead] < left) {
                    maxHead++;
                }
            }

            // 3. 更新答案
            f[i + 1] = (int) (sumF % MOD);
        }

        return f[n];
    }
}

###cpp

class Solution {
public:
    int countPartitions(vector<int>& nums, int k) {
        const int MOD = 1'000'000'007;
        int n = nums.size();
        deque<int> min_q, max_q;
        vector<int> f(n + 1);
        f[0] = 1;
        long long sum_f = 0; // 窗口中的 f[i] 之和
        int left = 0;

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 1. 入
            sum_f += f[i];

            while (!min_q.empty() && x <= nums[min_q.back()]) {
                min_q.pop_back();
            }
            min_q.push_back(i);

            while (!max_q.empty() && x >= nums[max_q.back()]) {
                max_q.pop_back();
            }
            max_q.push_back(i);

            // 2. 出
            while (nums[max_q.front()] - nums[min_q.front()] > k) {
                sum_f -= f[left];
                left++;
                if (min_q.front() < left) {
                    min_q.pop_front();
                }
                if (max_q.front() < left) {
                    max_q.pop_front();
                }
            }

            // 3. 更新答案
            f[i + 1] = sum_f % MOD;
        }

        return f[n];
    }
};

###go

func countPartitions(nums []int, k int) int {
const mod = 1_000_000_007
n := len(nums)
var minQ, maxQ []int
f := make([]int, n+1)
f[0] = 1
sumF := 0 // 窗口中的 f[i] 之和
left := 0

for i, x := range nums {
// 1. 入
sumF += f[i]

for len(minQ) > 0 && x <= nums[minQ[len(minQ)-1]] {
minQ = minQ[:len(minQ)-1]
}
minQ = append(minQ, i)

for len(maxQ) > 0 && x >= nums[maxQ[len(maxQ)-1]] {
maxQ = maxQ[:len(maxQ)-1]
}
maxQ = append(maxQ, i)

// 2. 出
for nums[maxQ[0]]-nums[minQ[0]] > k {
sumF -= f[left]
left++
if minQ[0] < left {
minQ = minQ[1:]
}
if maxQ[0] < left {
maxQ = maxQ[1:]
}
}

// 3. 更新答案
f[i+1] = sumF % mod
}
return f[n]
}

复杂度分析

  • 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。每个下标至多入队出队各两次。
  • 空间复杂度：$\mathcal{O}(n)$。

相似题目

更多相似题目，见下面动态规划题单的「§5.2 最优划分」和「§11.3 单调队列优化 DP」。

分类题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

❌
❌