Leetcode比赛时，快速解题的关键，是用好暴力解。即，选用思维最直观，（代码量相对较小），又在问题数据规模允许范围内的解，以最快的速度通过每道题。
那什么是赛时暴力解？思路是什么样的？和最优解之间差别在哪？正好Leetcode周赛252中，每道题都有对应的两种解法。我们来对比看下。
Leetcode周赛252，比赛时间，2023-07-02 10:30-12:00，对应题号 2760-2763
第一题 最长奇偶子数组
美服 2760 Longest Even Odd Subarray With Threshold
暴力解
暴力解非常直观，问的子数组，就遍历所有子数组（n^2）。然后再花n的复杂度去判断数组。整体时间复杂度O(n^3）。
暴力解的优势在于，我完全不用理解题干中列出的3个条件说了些啥。只管将题目翻译成代码就行。
class Solution:
def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
to_ret = 0
# 遍历子数组开头
for l in range(len(nums)) :
if not nums[l] % 2 == 0 :
continue # 条件检测1
# 遍历子数组结尾
for r in range(l, len(nums)) :
mark = True
for i in range(l, r) :
if not nums[i] % 2 != nums[i + 1] % 2 :
mark = False # 条件检测2
break
for i in range(l, r+1) :
if not nums[i] <= threshold :
mark = False # 条件检测3
break
if mark :
# 对满足条件的对象求最大
to_ret = max(to_ret, r-l+1)
return to_ret
最优解
仔细读一下题目中的条件，可以发现，条件1（nums[l] % 2 == 0 ）限定了子数组的开头，而在求最长子数组的语境下，条件2、3定义了子数组的中断条件。那就只需要顺序遍历，记录当前数为结尾的最长满足要求的子数组长度length，在中断时用length更新return，并依据条件更新length即可。
class Solution:
def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
nums.append(1e99) # 确保处理到最后一个数时最后一个可行区间被处理
to_ret = 0
length = 0
for i, t in enumerate(nums) :
if t > threshold or (i>0 and nums[i]%2==nums[i-1]%2) :
# 如果中断，就更新最长子数组
to_ret = max(to_ret, length)
length = 0
# 对满足条件的数，根据是否开头，对length操作逻辑略有差异
if t <= threshold :
if (length == 0 and t % 2 == 0) or length > 0:
length += 1
return to_ret
第二题 和等于目标值的质数对
美服 2761 Longest Even Odd Subarray With Threshold
暴力解
这题其实没什么说的。暴力解和最优解差不多，都挺暴力。
最简单的想法，用除法去判断一个数是否为素数。然后暴力去试。时间复杂度(n^1.5)
稍做些优化，感觉勉强能过。但结果是国服能过，美服过不了。
所以，把判断是否为素数的代码，放到全局变量，并加一个lru_cache做记忆化搜索：
# 判断vt是否为素数
@functools.lru_cache(None)
def isPrimes(vt) :
if vt > 2 and vt % 2 == 0 :
return False
for t in range(3, int(vt**0.5+1), 2) :
if vt % t == 0 :
return False
return True
class Solution:
def findPrimePairs(self, n: int) -> List[List[int]]:
to_ret = []
if n > 3 and isPrimes(n-2) :
to_ret.append([2, n-2])
if n % 2 == 0 :
for pt in range(3, n//2+1, 2) :
if isPrimes(pt) and isPrimes(n-pt) :
to_ret.append([pt, n-pt])
return to_ret
最优解
也挺暴力。主要思路在于，与其去逐一判断素数，不如在全局变量中去筛一个素数表。
def primes(maxv=10**6+1) :
to_ret = [0]*(maxv+1)
for p in range(2, int(maxv**0.5)+1) :
if to_ret[p] > 0 :
continue
for t in range(p*2, maxv+1, p) :
to_ret[t] += 1
return [t for t in range(2, maxv+1) if to_ret[t] == 0]
primes_list = sorted(primes())
primes_set = set(primes_list)
class Solution:
def findPrimePairs(self, n: int) -> List[List[int]]:
to_ret = []
for t in primes_list :
if t * 2 > n :
break
if n - t in primes_set :
to_ret.append([t, n-t])
return to_ret
第三题 不间断子数组
美服 2762 Continuous Subarrays
暴力解
先看数据范围，nlogn是可行的。
直观想法：长的就容易间断。那分治一下试试？
针对mid位置的数，我们只要O(n)地计算出所有包含该数的不间断子数组数量即可。
最大和最小差为2，不好。但如果确切地知道最大最小的范围呢？其实只有3种范围：num[mid]-2 ~ num[mid]，num[mid]-1 ~ num[mid]+1，num[mid] ~ num[mid]+2。然后暴力去做，都可以O(n)解决。
那三种范围有重叠的呢？简单容斥原理一下。
这个虽然代码长，但除了分治那里用了点脑子（其实也挺暴力），整体都很暴力。
长代码部分还可以复制粘贴。
class Solution:
def continuousSubarrays(self, nums: List[int]) -> int:
def solve(ps=0, pe=len(nums)-1) :
# 边界情况处理
if ps == pe :
return 1
if ps > pe :
return 0
# 中间数
mid = (ps + pe) // 2
# range1: -2 ~ 0
v1s, v1e = nums[mid]-2, nums[mid]
p1s = p1e = mid
while p1s > ps and v1s<=nums[p1s-1]<=v1e :
p1s -= 1
while p1e < pe and v1s<=nums[p1e+1]<=v1e :
p1e += 1
# range2: -1 ~ 1
v2s, v2e = nums[mid]-1, nums[mid]+1
p2s = p2e = mid
while p2s > ps and v2s<=nums[p2s-1]<=v2e :
p2s -= 1
while p2e < pe and v2s<=nums[p2e+1]<=v2e :
p2e += 1
# range3: 0 ~ 2
v3s, v3e = nums[mid], nums[mid]+2
p3s = p3e = mid
while p3s > ps and v3s<=nums[p3s-1]<=v3e :
p3s -= 1
while p3e < pe and v3s<=nums[p3e+1]<=v3e :
p3e += 1
# 容斥原理处理一下区间
to_ret = 0
to_ret += (p1e-mid+1) * (mid-p1s+1)
to_ret += (p2e-mid+1) * (mid-p2s+1)
to_ret += (p3e-mid+1) * (mid-p3s+1)
to_ret -= (min(p1e, p2e)-mid+1) * (mid-max(p1s, p2s)+1)
to_ret -= (min(p1e, p3e)-mid+1) * (mid-max(p1s, p3s)+1)
to_ret -= (min(p3e, p2e)-mid+1) * (mid-max(p3s, p2s)+1)
to_ret += (min(p3e, p2e, p1e)-mid+1) * (mid-max(p3s, p2s, p1s)+1)
# 分治：处理前后2段
to_ret += solve(ps, mid-1)
to_ret += solve(mid+1, pe)
return to_ret
return solve()
最优解
其实也可以算是另一个方向的暴力解，看对哪个知识点更熟悉了。我是感觉前一种方法更不用动脑子。
对于每个位置为结尾的不间断数组，我们去找开头应该在哪里。
而开头的位置如何确定？维护一个区间，确保区间最大和区间最小的差在2以内。（动脑子点1）
如何维护这个区间？需要两个懒删除的堆（动脑子点2）
class Solution:
def continuousSubarrays(self, nums: List[int]) -> int:
s = 0
heap_min = []
heap_max = []
delete_min = collections.Counter()
delete_max = collections.Counter()
to_ret = 0
for e, v in enumerate(nums) :
heapq.heappush(heap_min, v)
heapq.heappush(heap_max, -v)
while -heap_max[0] - heap_min[0] > 2 :
# 如果差大于2，需要删除
delete_min[nums[s]] += 1
delete_max[nums[s]] += 1
s += 1
while delete_min[heap_min[0]] :
delete_min[heap_min[0]] -= 1
heapq.heappop(heap_min)
while delete_max[-heap_max[0]] :
delete_max[-heap_max[0]] -= 1
heapq.heappop(heap_max)
to_ret += e - s + 1
return to_ret
利用s位置的特点，优化一下懒删除堆的写法。代码会变短，但因为把list丢到heap中，速度会变慢。
class Solution:
def continuousSubarrays(self, nums: List[int]) -> int:
s = 0
heap_min = []
heap_max = []
to_ret = 0
for e, v in enumerate(nums) :
heapq.heappush(heap_min, [v, e])
heapq.heappush(heap_max, [-v, e])
while -heap_max[0][0] - heap_min[0][0] > 2 :
# 如果差大于2，需要删除
s += 1
while heap_min[0][1] < s :
heapq.heappop(heap_min)
while heap_max[0][1] < s :
heapq.heappop(heap_max)
to_ret += e - s + 1
return to_ret
第四题 所有子数组中不平衡数字之和
美服 2763 Sum of Imbalance Numbers of All Subarrays
暴力解
（因为n=10^3，遍历所有子数组需要n^2，大概率会超时，所以转换思路）
遍历每个数（位置i的数v），看它能在多少个子数组中带来不平衡数字。
不平衡条件1：子数组中不包含v+1。记位置i和前一个v+1隔了a个数，和后一个v+1隔了b个数，所以有ab个子数组满足条件。
不平衡条件2：这ab个子数组，不光不包含v+1，还得包含至少是v+2的数。所以，假设位置i前c个数不超过v，后d个数不超过v，则答案是ab-cd。
时间复杂度n^2
class Solution:
def sumImbalanceNumbers(self, nums: List[int]) -> int:
to_ret = 0
for i, v in enumerate(nums) :
ps, pe = i, i
# v的部分，用于处理重复数字：数v带来的不平衡数字，算在第一个v的头上。
while ps > 0 and not nums[ps-1] == v and not nums[ps-1]==v+1 :
ps -= 1
while pe < len(nums)-1 and not nums[pe+1]==v+1 :
pe += 1
# rps与rpe：[rps, rpe]为[ps, pe]的子集，该范围内，没有比nums[i]要大的数。
# 因为nums[i]会是子数组里最大数，从而不会带来不平衡，需要删去。
rps, rpe = i, i
while rps > ps and nums[rps-1] <= v:
rps -= 1
while rpe < pe and nums[rpe+1] <= v:
rpe += 1
to_ret += (i-ps+1) * (pe-i+1) - (i-rps+1)*(rpe-i+1)
return to_ret
最优解
上文中，ps和pe的求法，可以通过预先遍历一遍nums（正向&反向）得到。
而rps与rpe的求法，可以通过单调栈的方式，遍历得到。
合并一些遍历过程之后，就得到了以下代码，时间复杂度O(n)：
class Solution:
def sumImbalanceNumbers(self, nums: List[int]) -> int:
v2i = {} # 储存上一次遍历的v对应的坐标i
next_p1 = {} # 储存位置i后一次，nums[i+1]出现的位置
next_g = {} # 储存位置i下一个，比nums[i]大的坐标
greater = [[1e99, len(nums)]]
for i in range(len(nums)-1, -1, -1) :
v = nums[i]
if (v+1) in v2i :
next_p1[i] = v2i[v+1]
v2i[v] = i
while v >= greater[-1][0] :
greater.pop(-1)
next_g[i]=greater[-1][1]
greater.append([v, i])
v2i = {} # 储存上一次遍历的v对应的坐标i
to_ret = 0
greater = [[1e99, -1]]
for i, v in enumerate(nums) :
# 上一次v出现的位置，后一个。
# 用于处理重复数字：数v带来的不平衡数字，算在第一个v的头上。
ps1 = v2i.get(v, -1) + 1
# 上一次v+1出现的位置，后一个
ps2 = v2i.get(v+1, -1) + 1
# 下一次v+1出现的位置，前一个
pe = next_p1.get(i, len(nums)) - 1
# 开始位置在[ps, i]，结束位置在[i, pe]之间的数组，包含位置i，且不包含数nums[i]+1
ps = max(ps1, ps2)
# rps与rpe：[rps, rpe]为[ps, pe]的子集，该范围内，没有比nums[i]要大的数。
# 因为nums[i]会是子数组里最大数，从而不会带来不平衡，需要删去。
while greater[-1][0] <= v :
greater.pop(-1)
rps, rpe = max(ps, greater[-1][1]+1), min(pe, next_g[i]-1)
# 计算结果：
to_ret += (i-ps+1) * (pe-i+1) - (i-rps+1)*(rpe-i+1)
v2i[v] = i
greater.append([v, i])
return to_ret
总结
总结一下，这几道题都有多种解法，比赛时暴力解可以一定程度节约时间：
- 第一题，暴力解解约了理解题意的时间，直接照着问题说的去模拟就好了。时间复杂度从O(n)上升到了O(n^3），但n=100，可以接受。
- 第二题，暴力解和最优解其实差别不大。暴力解的直观之处在于直接用“试除”去判断素数。在美服上，直接提交会TLE，再把试除部分记忆化之后放在全局变量中。最优解用到了素数筛法。
- 第三题，暴力解的思路就是从“分治”这两个字出发，一直莽。不管是整体的分治框架，还是根据数值范围的分类讨论，还是容斥原理的操作，代码虽长但不用思考，只管莽。最优解（可能不够优）时间复杂度相同，但用到了基于heap+懒删除操作去维护区间最大最小值，算法相对更高级（用线段树也可以，代码量就更大了）。
- 第四题，既然题目允许n^2，暴力解就是在一次遍历过程中，所有能用暴力O(n)解决的，都用暴力解决。而最优解，用了多次循环操作、单调栈等知识点，整体O(n)复杂度地解决了问题。
我们也能看到比赛时暴力解的一些特点与问题：
- “暴力”也不完全是事件复杂度更高，比如第三题的两种解法，时间复杂度相差不大，暴力解代码更长，但思维更直观。
- “暴力”有时也是相对的。比如第三题，哪个解法更节约时间，取决于对“懒删除heap维护区间最值”和“分治法”哪个更熟悉。
- “暴力”重点还是要过，所以也不是完全不考虑时间复杂度。比如第四题“因为n=10^3，遍历所有子数组需要n^2，大概率会超时，所以转换思路”。
- “暴力”也可能会带来额外的罚时。比如第二题，solution-1只在国服能过。
