解题思路
解题思路
给出一个数组,要求在这个数组中找出任意一段子区间的和,位于 [lower,upper] 之间。
这一题可以用暴力解法,2 层循环,遍历所有子区间,求和并判断是否位于 [lower,upper] 之间,时间复杂度 O(n^2)。
这一题当然还有更优的解法,用线段树或者树状数组,将时间复杂度降为 O(n log n)。题目中要求 lower ≤ sum(i,j) ≤ upper,sum(i,j) = prefixSum(j) - prefixSum(i-1),那么
lower + prefixSum(i-1) ≤ prefixSum(j) ≤ upper + prefixSum(i-1)。所以利用前缀和将区间和转换成了前缀和在线段树中 query 的问题,只不过线段树中父节点中存的不是子节点的
和,而应该是子节点出现的次数。第二个转换,由于前缀和会很大,所以需要离散化。例如 prefixSum = [-3,-2,-1,0],用前缀和下标进行离散化,所以线段树中左右区间变成了 0-3。

利用 prefixSum 下标离散化:

树中倒序插入 prefixSum 的时候,用的是非去重的,插入 prefixSum[j] 代表 sum(i,j) 中的 j,例如往线段树中插入 prefixSum[5],代表当前树中加入了 j = 5 的情况。query 操作实质是在做
区间匹配,例如当前 i 循环到 i = 3,累计往线段树中插入了 prefixSum[5],prefixSum[4],prefixSum[3],那么 query 操作实质是在判断:lower ≤
sum(i=3,j=3) ≤ upper,lower ≤ sum(i=3,j=4) ≤ upper,lower ≤ sum(i=3,j=5) ≤ upper,这 3 个等式是否成立,有几个成立就返回几个,即是最终要求得的结果的一部分。
举个例子,nums = [-3,1,2,-2,2,-1],prefixSum = [-3,-2,0,-2,0,-1],去重以后并排序得到 sum = [-3,-2,-1,0]。离散化构造线段树,这里出于演示的方便,下图中就不画出离散
后的线段树了,用非离散的线段树展示:

倒序插入 len(prefixSum)-1 = prefixSum[5] = -1:

这时候查找区间变为了 [-3 + prefixSum[5-1], -1 + prefixSum[5-1]] = [-3,-1],即判断 -3 ≤ sum(5,5) ≤ -1,满足等式的有几种情况,这里明显只有一种情况,即 j = 5,也满
足等式,所以这一步 res = 1。

这时候查找区间变为了 [-3 + prefixSum[4-1], -1 + prefixSum[4-1]] = [-5,-3],即判断 -5 ≤ sum(4,4,5) ≤ -3,满足等式的有几种情况,这里有两种情况,即 j = 4 或者 j =
5,都不满足等式,所以这一步 res = 0。
倒序插入 len(prefixSum)-3 = prefixSum[3] = -2:

这时候查找区间变为了 [-3 + prefixSum[3-1], -1 + prefixSum[3-1]] = [-3,-1],即判断 -3 ≤ sum(3,3,4,5) ≤ -1,满足等式的有几种情况,这里有三种情况,即 j = 3、j =
4 或者 j = 5,满足等式的有 j = 3 和 j = 5,即 -3 ≤ sum(3, 3) ≤ -1 和 -3 ≤ sum(3,
- ≤ -1。所以这一步 res = 2。
倒序插入 len(prefixSum)-4 = prefixSum[2] = 0:

这时候查找区间变为了 [-3 + prefixSum[2-1], -1 + prefixSum[2-1]] = [-5,-3],即判断 -5 ≤ sum(2,2,3,4,5) ≤ -3,满足等式的有几种情况,这里有四种情况,即 j = 2、 j
= 3、j = 4 或者 j = 5,都不满足等式。所以这一步 res = 0。
倒序插入 len(prefixSum)-5 = prefixSum[1] = -2:

这时候查找区间变为了 [-3 + prefixSum[1-1], -1 + prefixSum[1-1]] = [-6,-4],即判断 -6 ≤ sum(1,1,2,3,4,5) ≤ -4,满足等式的有几种情况,这里有五种情况,即 j = 1、
j = 2、 j = 3、j = 4 或者 j = 5,都不满足等式。所以这一步 res = 0。
倒序插入 len(prefixSum)-6 = prefixSum[0] = -3:
全站分卷索引 · 484 卷
- 1关于书的封面
- 2目标读者
- 3第二章 算法专题
- 4Array
- 5Backtracking
- 6Binary Indexed Tree
- 7Bit Manipulation
- 8Breadth First Search
- 9Depth First Search
- 10Dynamic Programming
- 11Hash Table
- 12Linked List
- 13Math
- 14Segment Tree
- 15Sliding Window
- 16Sort
- 17Stack
- 18String
- 19Tree
- 20Two Pointers
- 21Union Find
- 22第三章 一些模板
- 23并查集 UnionFind
- 24第四章 Leetcode 题解
- 251. Two Sum
- 26题目大意
- 27题目大意
- 283. Longest Substring Without Repeating Characters
- 29题目大意
- 304. Median of Two Sorted Arrays
- 31题目大意
- 32代码
- 337. Reverse Integer
- 34解题思路
- 35题目大意
- 3611. Container With Most Water
- 3713. Roman to Integer
- 38题目大意
- 39解题思路
- 4015. 3Sum
- 41代码
- 42题目
- 4317. Letter Combinations of a Phone Number
- 44题目大意
- 4518. 4Sum
- 46题目大意
- 4719. Remove Nth Node From End of List
- 4820. Valid Parentheses
- 49题目大意
- 50题目大意
- 51题目
- 5223. Merge k Sorted Lists
- 5324. Swap Nodes in Pairs
- 54解题思路
- 5525. Reverse Nodes in k-Group
- 5626. Remove Duplicates from Sorted Array
- 57题目大意
- 5827. Remove Element
- 59题目大意
- 6028. Implement strStr()
- 6129. Divide Two Integers
- 62题目大意
- 6330. Substring with Concatenation of All Words
- 6433. Search in Rotated Sorted Array
- 65代码
- 66题目
- 6735. Search Insert Position
- 68题目大意
- 69题目大意
- 7037. Sudoku Solver
- 71题目大意
- 72代码
- 7339. Combination Sum
- 74题目大意
- 7540. Combination Sum II
- 76解题思路
- 7741. First Missing Positive
- 7842. Trapping Rain Water
- 79代码
- 8046. Permutations
- 8147. Permutations II
- 82解题思路
- 8348. Rotate Image
- 84解题思路
- 8549. Group Anagrams
- 86题目大意
- 8750. Pow(x, n)
- 8851. N-Queens
- 89题目大意
- 9052. N-Queens II
- 91题目大意
- 9253. Maximum Subarray
- 9354. Spiral Matrix
- 94题目大意
- 9555. Jump Game
- 9656. Merge Intervals
- 9757. Insert Interval
- 98解题思路
- 9959. Spiral Matrix II
- 10060. Permutation Sequence
- 101题目大意
- 10261. Rotate List
- 103题目大意
- 10462. Unique Paths
- 105题目大意
- 10663. Unique Paths II
- 107解题思路
- 108题目大意
- 10966. Plus One
- 110题目大意
- 11167. Add Binary
- 11269. Sqrt(x)
- 113题目大意
- 114代码
- 11570. Climbing Stairs
- 116题目大意
- 117题目大意
- 11874. Search a 2D Matrix
- 119解题思路
- 120题目大意
- 12176. Minimum Window Substring
- 12277. Combinations
- 123题目大意
- 12478. Subsets
- 12579. Word Search
- 12680. Remove Duplicates from Sorted Array II
- 127题目大意
- 12881. Search in Rotated Sorted Array II
- 129解题思路
- 13082. Remove Duplicates from Sorted List II
- 13183. Remove Duplicates from Sorted List
- 13284. Largest Rectangle in Histogram
- 133题目大意
- 13486. Partition List
- 135代码
- 13688. Merge Sorted Array
- 137题目大意
- 13889. Gray Code
- 139代码
- 14090. Subsets II
- 141解题思路
- 14291. Decode Ways
- 143代码
- 144题目大意
- 14593. Restore IP Addresses
- 14694. Binary Tree Inorder Traversal
- 147题目大意
- 14895. Unique Binary Search Trees II
- 14996. Unique Binary Search Trees
- 150题目大意
- 15198. Validate Binary Search Tree
- 15299. Recover Binary Search Tree
- 153题目大意
- 154100. Same Tree
- 155题目大意
- 156101. Symmetric Tree
- 157102. Binary Tree Level Order Traversal
- 158解题思路
- 159103. Binary Tree Zigzag Level Order Traversal
- 160题目大意
- 161104. Maximum Depth of Binary Tree
- 162题目大意
- 163题目大意
- 164106. Construct Binary Tree from Inorder and Postorder Traversal
- 165解题思路
- 166题目大意
- 167108. Convert Sorted Array to Binary Search Tree
- 168109. Convert Sorted List to Binary Search Tree
- 169解题思路
- 170110. Balanced Binary Tree
- 171题目大意
- 172111. Minimum Depth of Binary Tree
- 173112. Path Sum
- 174代码
- 175题目大意
- 176114. Flatten Binary Tree to Linked List
- 177题目大意
- 178代码
- 179120. Triangle
- 180121. Best Time to Buy and Sell Stock
- 181题目大意
- 182122. Best Time to Buy and Sell Stock II
- 183题目大意
- 184题目
- 185125. Valid Palindrome
- 186题目大意
- 187126. Word Ladder II
- 188题目大意
- 189127. Word Ladder
- 190题目大意
- 191解题思路
- 192128. Longest Consecutive Sequence
- 193代码
- 194129. Sum Root to Leaf Numbers
- 195题目大意
- 196130. Surrounded Regions
- 197题目大意
- 198131. Palindrome Partitioning
- 199136. Single Number
- 200题目大意
- 201题目大意
- 202代码
- 203141. Linked List Cycle
- 204代码
- 205143. Reorder List
- 206代码
- 207144. Binary Tree Preorder Traversal
- 208题目
- 209145. Binary Tree Postorder Traversal
- 210147. Insertion Sort List
- 211题目大意
- 212148. Sort List
- 213150. Evaluate Reverse Polish Notation
- 214题目大意
- 215151. Reverse Words in a String
- 216题目大意
- 217题目
- 218153. Find Minimum in Rotated Sorted Array
- 219154. Find Minimum in Rotated Sorted Array II
- 220解题思路
- 221题目大意
- 222160. Intersection of Two Linked Lists
- 223题目大意
- 224162. Find Peak Element
- 225题目大意
- 226164. Maximum Gap
- 227题目大意
- 228167. Two Sum II - Input array is sorted
- 229题目大意
- 230168. Excel Sheet Column Title
- 231解题思路
- 232题目大意
- 233171. Excel Sheet Column Number
- 234172. Factorial Trailing Zeroes
- 235代码
- 236题目大意
- 237174. Dungeon Game
- 238题目大意
- 239代码
- 240179. Largest Number
- 241题目大意
- 242187. Repeated DNA Sequences
- 243题目大意
- 244190. Reverse Bits
- 245题目大意
- 246题目大意
- 247198. House Robber
- 248解题思路
- 249199. Binary Tree Right Side View
- 250代码
- 251200. Number of Islands
- 252201. Bitwise AND of Numbers Range
- 253题目大意
- 254202. Happy Number
- 255代码
- 256解题思路
- 257题目大意
- 258题目大意
- 259206. Reverse Linked List
- 260207. Course Schedule
- 261题目大意
- 262208. Implement Trie (Prefix Tree)
- 263209. Minimum Size Subarray Sum
- 264210. Course Schedule II
- 265题目大意
- 266211. Add and Search Word - Data structure design
- 267解题思路
- 268212. Word Search II
- 269题目大意
- 270题目大意
- 271215. Kth Largest Element in an Array
- 272代码
- 273题目大意
- 274217. Contains Duplicate
- 275题目大意
- 276题目大意
- 277代码
- 278219. Contains Duplicate II
- 279220. Contains Duplicate III
- 280解题思路
- 281222. Count Complete Tree Nodes
- 282题目大意
- 283223. Rectangle Area
- 284题目大意
- 285题目大意
- 286225. Implement Stack using Queues
- 287题目
- 288226. Invert Binary Tree
- 289题目大意
- 290229. Majority Element II
- 291230. Kth Smallest Element in a BST
- 292题目大意
- 293题目大意
- 294232. Implement Queue using Stacks
- 295题目大意
- 296234. Palindrome Linked List
- 297题目大意
- 298235. Lowest Common Ancestor of a Binary Search Tree
- 299题目大意
- 300代码
- 301题目大意
- 302237. Delete Node in a Linked List
- 303解题思路
- 304题目大意
- 305240. Search a 2D Matrix II
- 306题目大意
- 307242. Valid Anagram
- 308题目大意
- 309257. Binary Tree Paths
- 310258. Add Digits
- 311260. Single Number III
- 312代码
- 313题目大意
- 314题目大意
- 315题目大意
- 316275. H-Index II
- 317题目大意
- 318283. Move Zeroes
- 319287. Find the Duplicate Number
- 320解题思路
- 321290. Word Pattern
- 322题目大意
- 323300. Longest Increasing Subsequence
- 324解题思路
- 325303. Range Sum Query - Immutable
- 326解题思路
- 327306. Additive Number
- 328题目大意
- 329307. Range Sum Query - Mutable
- 330解题思路
- 331309. Best Time to Buy and Sell Stock with Cooldown
- 332题目大意
- 333代码
- 334315. Count of Smaller Numbers After Self
- 335318. Maximum Product of Word Lengths
- 336题目大意
- 337322. Coin Change
- 338题目大意
- 339题目大意
- 340代码
- 341326. Power of Three
- 342题目大意
- 343327. Count of Range Sum
- 344解题思路
- 345代码
- 346328. Odd Even Linked List
- 347题目大意
- 348329. Longest Increasing Path in a Matrix
- 349题目大意
- 350331. Verify Preorder Serialization of a Binary Tree
- 351题目大意
- 352337. House Robber III
- 353题目大意
- 354338. Counting Bits
- 355342. Power of Four
- 356343. Integer Break
- 357代码
- 358题目大意
- 359题目大意
- 360347. Top K Frequent Elements
- 361349. Intersection of Two Arrays
- 362350. Intersection of Two Arrays II
- 363代码
- 364解题思路
- 365357. Count Numbers with Unique Digits
- 366代码
- 367题目大意
- 368题目大意
- 369题目大意
- 370373. Find K Pairs with Smallest Sums
- 371解题思路
- 372378. Kth Smallest Element in a Sorted Matrix
- 373代码
- 374385. Mini Parser
- 375题目大意
- 376386. Lexicographical Numbers
- 377387. First Unique Character in a String
- 378389. Find the Difference
- 379392. Is Subsequence
- 380解题思路
- 381题目
- 382解题思路
- 383394. Decode String
- 384397. Integer Replacement
- 385题目大意
- 386代码
- 387题目大意
- 388代码
- 389401. Binary Watch
- 390题目大意
- 391解题思路
- 392402. Remove K Digits
- 393题目大意
- 394题目大意
- 395题目
- 396代码
- 397题目大意
- 398题目大意
- 399412. Fizz Buzz
- 400题目大意
- 401414. Third Maximum Number
- 402解题思路
- 403题目大意
- 404421. Maximum XOR of Two Numbers in an Array
- 405代码
- 406424. Longest Repeating Character Replacement
- 407题目大意
- 408433. Minimum Genetic Mutation
- 409题目大意
- 410435. Non-overlapping Intervals
- 411题目大意
- 412436. Find Right Interval
- 413题目大意
- 414437. Path Sum III
- 415代码
- 416题目大意
- 417代码
- 418441. Arranging Coins
- 419代码
- 420解题思路
- 421447. Number of Boomerangs
- 422题目大意
- 423448. Find All Numbers Disappeared in an Array
- 424451. Sort Characters By Frequency
- 425题目大意
- 426453. Minimum Moves to Equal Array Elements
- 427题目大意
- 428题目大意
- 429455. Assign Cookies
- 430题目大意
- 431题目大意
- 432457. Circular Array Loop
- 433题目大意
- 434461. Hamming Distance
- 435题目大意
- 436题目大意
- 437470. Implement Rand10() Using Rand7()
- 438题目大意
- 439代码
- 440题目大意
- 441475. Heaters
- 442题目大意
- 443476. Number Complement
- 444477. Total Hamming Distance
- 445解题思路
- 446题目大意
- 447代码
- 448483. Smallest Good Base
- 449题目大意
- 450代码
- 451485. Max Consecutive Ones
- 452代码
- 453解题思路
- 454493. Reverse Pairs
- 455代码
- 456494. Target Sum
- 457代码
- 458496. Next Greater Element I
- 459题目大意
- 460497. Random Point in Non-overlapping Rectangles
- 461解题思路
- 462498. Diagonal Traverse
- 463题目大意
- 464解题思路
- 465500. Keyboard Row
- 466题目大意
- 467题目
- 468507. Perfect Number
- 469题目大意
- 470508. Most Frequent Subtree Sum
- 471509. Fibonacci Number
- 472题目大意
- 473513. Find Bottom Left Tree Value
- 474解题思路
- 475515. Find Largest Value in Each Tree Row
- 476524. Longest Word in Dictionary through Deleting
- 477代码
- 478题目大意
- 479528. Random Pick with Weight
- 480题目大意
- 481代码
- 482529. Minesweeper
- 483题目大意
- 484解题思路