友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Prefix Sum 前缀和

经典题目

  1. 209. 长度最小的子数组

  2. 238. Product of Array Except Self

  3. [0253-meeting-rooms-ii]

  4. 303. Range Sum Query - Immutable

  5. 304. Range Sum Query 2D - Immutable

  6. [0325-maximum-size-subarray-sum-equals-k]

  7. [0363-max-sum-of-rectangle-no-larger-than-k]

  8. 370. Range Addition

  9. [0410-split-array-largest-sum]

  10. [0497-random-point-in-non-overlapping-rectangles]

  11. 523. Continuous Subarray Sum

  12. [0525-contiguous-array]

  13. 528. Random Pick with Weight

  14. [0548-split-array-with-equal-sum]

  15. 560. Subarray Sum Equals K

  16. [0644-maximum-average-subarray-ii]

  17. [0689-maximum-sum-of-3-non-overlapping-subarrays]

  18. 713. Subarray Product Less Than K

  19. 724. Find Pivot Index

  20. [0731-my-calendar-ii]

  21. [0732-my-calendar-iii]

  22. [0798-smallest-rotation-with-highest-score]

  23. [0813-largest-sum-of-averages]

  24. [0848-shifting-letters]

  25. [0862-shortest-subarray-with-sum-at-least-k]

  26. [0903-valid-permutations-for-di-sequence]

  27. [0930-binary-subarrays-with-sum]

  28. [0974-subarray-sums-divisible-by-k]

  29. [0995-minimum-number-of-k-consecutive-bit-flips]

  30. [1000-minimum-cost-to-merge-stones]

  31. [1004-max-consecutive-ones-iii]

  32. [1074-number-of-submatrices-that-sum-to-target]

  33. 1094. Car Pooling

  34. 1109. Corporate Flight Bookings

  35. [1124-longest-well-performing-interval]

  36. [1140-stone-game-ii]

  37. [1177-can-make-palindrome-from-substring]

  38. [1208-get-equal-substrings-within-budget]

  39. [1248-count-number-of-nice-subarrays]

  40. [1292-maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold]

  41. [1310-xor-queries-of-a-subarray]

  42. [1314-matrix-block-sum]

  43. [1352-product-of-the-last-k-numbers]

  44. [1371-find-the-longest-substring-containing-vowels-in-even-counts]

  45. [1413-minimum-value-to-get-positive-step-by-step-sum]

  46. [1420-build-array-where-you-can-find-the-maximum-exactly-k-comparisons]

  47. [1422-maximum-score-after-splitting-a-string]

  48. [1423-maximum-points-you-can-obtain-from-cards]

  49. [1442-count-triplets-that-can-form-two-arrays-of-equal-xor]

  50. [1444-number-of-ways-of-cutting-a-pizza]

  51. 1480. Running Sum of 1d Array

  52. [1508-range-sum-of-sorted-subarray-sums]

  53. [1524-number-of-sub-arrays-with-odd-sum]

  54. [1546-maximum-number-of-non-overlapping-subarrays-with-sum-equals-target]

  55. [1588-sum-of-all-odd-length-subarrays]

  56. [1589-maximum-sum-obtained-of-any-permutation]

  57. [1590-make-sum-divisible-by-p]

  58. [1658-minimum-operations-to-reduce-x-to-zero]

  59. [1664-ways-to-make-a-fair-array]

  60. [1674-minimum-moves-to-make-array-complementary]

  61. [1685-sum-of-absolute-differences-in-a-sorted-array]

  62. [1687-delivering-boxes-from-storage-to-ports]

  63. [1703-minimum-adjacent-swaps-for-k-consecutive-ones]

  64. [1712-ways-to-split-array-into-three-subarrays]

  65. [1732-find-the-highest-altitude]

  66. [1737-change-minimum-characters-to-satisfy-one-of-three-conditions]

  67. [1738-find-kth-largest-xor-coordinate-value]

  68. [1744-can-you-eat-your-favorite-candy-on-your-favorite-day]

  69. [1769-minimum-number-of-operations-to-move-all-balls-to-each-box]

  70. [1788-maximize-the-beauty-of-the-garden]

  71. [1829-maximum-xor-for-each-query]

  72. [1838-frequency-of-the-most-frequent-element]

  73. [1854-maximum-population-year]

  74. [1856-maximum-subarray-min-product]

  75. [1862-sum-of-floored-pairs]

  76. [1871-jump-game-vii]

  77. [1872-stone-game-viii]

  78. [1878-get-biggest-three-rhombus-sums-in-a-grid]

  79. [1889-minimum-space-wasted-from-packaging]

  80. [1893-check-if-all-the-integers-in-a-range-are-covered]

  81. [1894-find-the-student-that-will-replace-the-chalk]

  82. [1895-largest-magic-square]

  83. [1915-number-of-wonderful-substrings]

  84. [1930-unique-length-3-palindromic-subsequences]

  85. [1943-describe-the-painting]

  86. [1983-widest-pair-of-indices-with-equal-range-sum]

  87. [1991-find-the-middle-index-in-array]

  88. [2017-grid-game]

  89. [2021-brightest-position-on-street]

  90. [2024-maximize-the-confusion-of-an-exam]

  91. [2025-maximum-number-of-ways-to-partition-an-array]

  92. [2055-plates-between-candles]

  93. [2083-substrings-that-begin-and-end-with-the-same-letter]

  94. [2100-find-good-days-to-rob-the-bank]

  95. [2106-maximum-fruits-harvested-after-at-most-k-steps]

  96. [2121-intervals-between-identical-elements]

  97. [2132-stamping-the-grid]

  98. [2145-count-the-hidden-sequences]

  99. [2171-removing-minimum-number-of-magic-beans]

  100. [2207-maximize-number-of-subsequences-in-a-string]

  101. [2209-minimum-white-tiles-after-covering-with-carpets]

  102. [2218-maximum-value-of-k-coins-from-piles]

  103. [2219-maximum-sum-score-of-array]

  104. [2222-number-of-ways-to-select-buildings]

  105. [2234-maximum-total-beauty-of-the-gardens]

  106. [2237-count-positions-on-street-with-required-brightness]

  107. [2245-maximum-trailing-zeros-in-a-cornered-path]

  108. [2251-number-of-flowers-in-full-bloom]

  109. [2256-minimum-average-difference]

  110. [2270-number-of-ways-to-split-array]

  111. [2271-maximum-white-tiles-covered-by-a-carpet]

  112. [2281-sum-of-total-strength-of-wizards]

  113. [2302-count-subarrays-with-score-less-than-k]

  114. [2381-shifting-letters-ii]

  115. [2382-maximum-segment-sum-after-removals]

  116. [2389-longest-subsequence-with-limited-sum]

  117. [2391-minimum-amount-of-time-to-collect-garbage]

  118. [2398-maximum-number-of-robots-within-budget]

  119. [2406-divide-intervals-into-minimum-number-of-groups]

  120. [2420-find-all-good-indices]

  121. [2428-maximum-sum-of-an-hourglass]

  122. [2438-range-product-queries-of-powers]

  123. [2439-minimize-maximum-of-array]

  124. [2448-minimum-cost-to-make-array-equal]

  125. [2483-minimum-penalty-for-a-shop]

  126. [2485-find-the-pivot-integer]

  127. [2488-count-subarrays-with-median-k]

  128. [2489-number-of-substrings-with-fixed-ratio]

  129. [2528-maximize-the-minimum-powered-city]

  130. [2536-increment-submatrices-by-one]

  131. [2552-count-increasing-quadruplets]

  132. [2559-count-vowel-strings-in-ranges]

  133. [2574-left-and-right-sum-differences]

  134. [2587-rearrange-array-to-maximize-prefix-score]

  135. [2588-count-the-number-of-beautiful-subarrays]

  136. [2602-minimum-operations-to-make-all-array-elements-equal]

  137. [2615-sum-of-distances]

  138. [2640-find-the-score-of-all-prefixes-of-an-array]

  139. [2680-maximum-or]

  140. [2681-power-of-heroes]

  141. [2731-movement-of-robots]

  142. [2772-apply-operations-to-make-all-array-elements-equal-to-zero]

  143. [2819-minimum-relative-loss-after-buying-chocolates]

  144. [2838-maximum-coins-heroes-can-collect]

  145. [2845-count-of-interesting-subarrays]

  146. [2848-points-that-intersect-with-cars]

  147. [2875-minimum-size-subarray-in-infinite-array]

  148. [2906-construct-product-matrix]

  149. [2947-count-beautiful-substrings-i]

  150. [2949-count-beautiful-substrings-ii]

  151. [2950-number-of-divisible-substrings]

  152. [2955-number-of-same-end-substrings]

  153. [2968-apply-operations-to-maximize-frequency-score]

  154. [2971-find-polygon-with-the-largest-perimeter]

  155. [2983-palindrome-rearrangement-queries]

  156. [3015-count-the-number-of-houses-at-a-certain-distance-i]

  157. [3017-count-the-number-of-houses-at-a-certain-distance-ii]

  158. [3026-maximum-good-subarray-sum]

  159. [3028-ant-on-the-boundary]

  160. [3070-count-submatrices-with-top-left-element-and-sum-less-than-k]

  161. [3077-maximum-strength-of-k-disjoint-subarrays]

  162. [3086-minimum-moves-to-pick-k-ones]

  163. [3096-minimum-levels-to-gain-more-points]

  164. [3104-find-longest-self-contained-substring]

  165. [3129-find-all-possible-stable-binary-arrays-i]

  166. [3130-find-all-possible-stable-binary-arrays-ii]

  167. [3147-taking-maximum-energy-from-the-mystic-dungeon]

  168. [3152-special-array-ii]

  169. [3179-find-the-n-th-value-after-k-seconds]

  170. [3191-minimum-operations-to-make-binary-array-elements-equal-to-one-i]

  171. [3212-count-submatrices-with-equal-frequency-of-x-and-y]

  172. [3224-minimum-array-changes-to-make-differences-equal]

  173. [3225-maximum-score-from-grid-operations]

  174. [3250-find-the-count-of-monotonic-pairs-i]

  175. [3251-find-the-count-of-monotonic-pairs-ii]

  176. [3261-count-substrings-that-satisfy-k-constraint-ii]

  177. [3279-maximum-total-area-occupied-by-pistons]

  178. [3312-sorted-gcd-pair-queries]

  179. [3333-find-the-original-typed-string-ii]

  180. [3346-maximum-frequency-of-an-element-after-performing-operations-i]

  181. [3347-maximum-frequency-of-an-element-after-performing-operations-ii]

  182. [3354-make-array-elements-equal-to-zero]

  183. [3355-zero-array-transformation-i]

  184. [3356-zero-array-transformation-ii]

  185. [3361-shift-distance-between-two-strings]

  186. [3362-zero-array-transformation-iii]

  187. [3364-minimum-positive-sum-subarray]

  188. [3381-maximum-subarray-sum-with-length-divisible-by-k]

  189. [3413-maximum-coins-from-k-consecutive-bags]

  190. [3425-longest-special-path]

  191. [3427-sum-of-variable-length-subarrays]

  192. [3432-count-partitions-with-even-sum-difference]

  193. [3434-maximum-frequency-after-subarray-operation]

  194. [3445-maximum-difference-between-even-and-odd-frequency-ii]

  195. [3473-sum-of-k-subarrays-with-length-at-least-m]

  196. [3480-maximize-subarrays-after-removing-one-conflicting-pair]

  197. [3486-longest-special-path-ii]

  198. [3494-find-the-minimum-amount-of-time-to-brew-potions]

  199. [3500-minimum-cost-to-divide-array-into-subarrays]

参考资料

← Previous: Difference Array 差分数组 | ↑ Up: LeetCode 解题笔记 | Next: Merge Intervals 区间合并 →