HOME

你有一个整数数组 nums，你需要实现一个程序处理下面两种类型的多次查询：

• 更新：更新数组中某个字段的值；
• 求和：通过下标 left 和 right 查询区间 [left, right] 的和，其中 left <= right。

看到求和或许你开始思考能否用前缀和解题，但是题目要求能对原数组进行更新，显然前缀和不是最好的方案。这题可以运用线段树解决。

你有一个 2D 矩阵 matrix，你需要实现一个程序处理多次子矩阵求和的查询。

每次查询你会得到 2 个坐标，分别代表子矩阵的左上坐标和右下坐标，返回这个子矩阵的和。

典型的前缀和问题，所以我们讨论如何应用前缀和解决这道题。

你有一个整数数组 nums，你需要实现一个程序处理范围求和的查询

每次查询得到两个下标 left 和 right 作为参数，查询区间 [left, right] 的和，其中 left <= right。

前缀和的教学题，我们讨论前缀和如何解决这道题。

计算所有小于非负整数 n 的质数的数量。

质数（Prime）： 只能被 1 和其本身整除的数。

可以暴力、枚举解题，也可以找到一定规律优化一下暴力算法。

给定一个整数数组 nums，你需要将其排序后，找到相邻两个数之间的最大间隙（差）。如果不足两个元素则返回 0。

你必须在线性时间内，仅使用线性额外空间完成计算。

演算反向波兰表示法。反向波兰表示法是一种为减少内存访问的使用 Stack 的演算表达法，这种方法按照先操作对象后操作符的方式表达算术运算。

所以我们讨论如何使用 Stack 解决这道题。

遍历树通常有三种方法，分别是前序遍历（pre-order traversal）、中序遍历（in-order traversal）和后序遍历（post-order traversal）。这道题是后序遍历。

遍历树有三种方法，分别是前序 pre-order、中序 in-order 和后序 post-order 遍历。这道题是前序遍历。

前序遍历的递归写法没有难度。

分糖果 🍬 问题。有 n 个小朋友站成一排，每个人被分配一个分值，现在你要给他们分糖果，有两个要求。

1. 每个小朋友至少要有一个糖果 🍬；
2. 分数高的小朋友要比两边分数低的小朋友糖果 🍬 多。

你需要找到一个分配方案需要最少的糖果 🍬 数量。

你有一个未排序的整数数组 nums，你要在 O(n) 时间复杂度内找到最长的连续子序列，返回其长度

nums 数组的元素可以构成诺干个连续的子数组，我们需要找到最大的子数组，返回其长度。

思路

要找到最大的子数组，首先我们要找到子数组的第一个元素，可以将 nums 转成一个 HashSet，然后遍历它：

• 查询每个元素的前一个值（n - 1）是否存在；
  • 存在则表示这个元素不是子数组的最小值，直接跳过；
  • 不存在时，循环查询这个值的下一个值是否存在（n + 1），直到下一个值不存在为止；
  • 在查询下一个值的过程中保持一个计数器，一直计数到不存在下一个值；
  • 将其和全局变量取一个最大值；
• 返回全局最大值。

因为我们只在子数组的最小值开始遍历，所以能避免不需要的运算，让时间复杂度在 O(n)。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        ans, nums = 0, set(nums)
        for n in nums:
            if n - 1 not in nums:
                count = 1
                while n + 1 in nums:
                    n, count = n + 1, count + 1
                ans = max(ans, count)
        return ans