shi0rik0 的博客shi0rik0 的博客
主页
所有文章
按类别浏览
按标签浏览
主页
所有文章
按类别浏览
按标签浏览
ACGN 1pinia 1electron 2理财 1神经网络 1transformer 1npm 1WSL 1算法八股文 7滑动窗口 1前缀和 1前缀树 1树状数组 1VuePress 1
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]。