shi0rik0 的博客shi0rik0 的博客
主页
所有文章
按类别浏览
按标签浏览
Ubuntu 实用脚本
Next.js 配置脚本
主页
所有文章
按类别浏览
按标签浏览
Ubuntu 实用脚本
Next.js 配置脚本
ACGN 1pinia 1electron 2理财 1神经网络 1transformer 1npm 1WSL 1算法八股文 7滑动窗口 1前缀和 1前缀树 1树状数组 1SSE 1Linux 1VS Code 1VuePress 1Spring 2
LeetCode题解:字母与数字

Date: 6/3/2025Category: Tag: 算法八股文, 前缀和

题目链接:https://leetcode.cn/problems/find-longest-subarray-lcci/

解题思路

这道题可以转化为一个经典的问题:在一个数组中找到和为k的最长子数组。我们只要将数组中的字母替换成1,数字替换成-1,那么原题就变成了在一个数组中找到和为0的最长子数组。

要解决这个问题,我们需要用到一个叫做“前缀和”的技巧。我们用sum(i, j)表示数组在区间[i, j)上的和(sum(i, i) = 0),如果令数组prefix[i] = sum(0, i),那么就可以快速计算出sum(i, j) = prefix[j] - prefix[i]。