Pan's algorithm notes
  • Introduction
  • My Notes
    • Introduction
    • Content table
    • 1 Sliding window
      • 1918 Kth Smallest Subarray Sum
      • 713 Subarray Product Less Than K
      • 438 Find All Anagrams in a String
      • 76 Minimum Window Substring
      • 159 Longest Substring with At Most Two Distinct Characters
      • 340 Longest Substring with At Most K Distinct Characters
      • 3 Longest Substring Without Repeating Characters
      • 209 Minimum Size Subarray Sum
      • 395 Longest Substring with At Least K Repeating Characters
      • L604 Window Sum
      • 1658 Minimum Operations to Reduce X to Zero
      • 346 Moving Average from Data Stream
      • 567 Permutation in String
    • 2 Rotated Arrays
      • L1790 Rotate String II
      • L39 Recover Rotated Sorted Array
      • L62 Search in Rotated Sorted Array
      • L63 Search in Rotated Sorted Array II
      • L159 Find Minimum in Rotated Sorted Array
      • L160 Find Minimum in Rotated Sorted Array II
      • 189 Rotate Array
      • L53 Reverse Words in a String
      • 151 Reverse Words in a String
      • 186 Reverse Words in a String II
      • 557 Reverse Words in a String III
    • 3 Permutation & Combination
      • 784 Letter Case Permutation
      • 526 Beautiful Arrangement
      • L15 Permutation
      • L16 Permutation II
      • L17 Subsets
      • L18 Subsets II
      • 254 Factor Combinations
      • 39 Combination Sum (L135)
      • 40 Combination Sum II
      • 216 Combination Sum III
      • 77 Combinations
      • 17 Letter Combination of a Phone Number
      • L10 String Permutation II
      • 267 Palindrome Permutaion II
    • 4 Palindrome
      • 336 Palindrome Pairs
      • 409 Longest Palindrome
      • 1332 Remove Palindromic Subsequences
      • 266 Palindrome Permuation
      • 5 Longest Palindromic Substring
      • 516 Longest Palindromic Subsequence
      • 647 Palindromic Substrings
      • 730 Count Different Palindromic Subsequences
    • 5 Quick Sort + Partition
      • 912 Sort an Array
      • 345 Reverse Vowels of a String
      • 125 Valid Palindrome
      • L31 Partition Array
      • 75 Sort colors
      • L143 Sort Colors II
      • L373 Partition Array by Odd and Even
      • L49 Sort Letters by Case
      • L5 Kth Largest Element
      • 86 Partition List
      • 414 Third Maximum Number
      • 280 Wiggle Sort
      • 324 Wiggle Sort II
      • 747 Largest Number At Least Twice of Others
      • L399 Nuts & bolts Problem
      • 917 Reverse Only Letters
    • 6 Matrix
      • 1380 Lucky Numbers in a Matrix
      • 48 Rotate Image
      • 亚麻题库的rotate matrix
      • 54 Spiral Matrix
      • 59 Spiral Matrix II
      • 73 Set Matrix Zeroes
      • L185 Matrix Zigzag Traversal
    • 7 Subarrays (prefix sum)
      • 560 Subarray Sum Equals K
      • 1477 Find Two Non-overlapping Sub-arrays Each With Target Sum
      • 528 Random Pick with Weight
      • L41 Maximum Subarray
      • L42 Maximum Subarray II
      • L44 Minimum Subarray
      • L45 Maximum Subarray Difference
      • 304 Range Sum Query 2D - immutable
      • 303 Range Sum Query - immutable
      • L138 Subarray Sum
      • L405 Submatrix Sum
      • L558 Sliding Window Matrix Maximum
      • L139 Subarray Sum Closest
      • L402 Continuous Subarray Sum
      • L403 Continuous Subarray Sum II
      • L404 Subarray Sum II
      • 325 Maximum Size Subarray Sum Equals k
      • 523 Continuous Subarray Sum
      • 724 Find Pivot Index
    • 8 Intervals
      • 56 Merge Intervals
      • 57 Insert Intervals
      • 436 Find Right Intervals
      • 352 Data Stream as Disjoint Intervals
      • 435 Non-overlapping Intervals
      • 228 Summary Ranges
      • 252 Meeting Rooms
      • 163 Missing Range
    • 9 Stocks
      • 714 Best Time to Buy and Sell Stock with Transaction Fee
      • L149 Best Time to Buy and Sell Stock
      • L150 Best Time to Buy and Sell Stock II
      • L151 Best Time to Buy and Sell Stock III
      • L393 Best Time to Buy and Sell Stock IV
    • 10 2，3，4 Sums
      • 1099 Two Sum Less Than K
      • 2491 Divide Players Into Teams of Equal Skill
      • 633 Sum of Square Numbers
      • 1679 Max Number of K-Sum Pairs
      • 1 Two Sum
      • 167 Two Sum II - input array is sorted
      • L443 Two Sum II - use 2 pointer to count
      • 170 Two Sum III - Data structure design
      • L553 Two Sum Closest
      • 15 3 Sum
      • 16 3 Sum Closest
      • 18 4 Sum
      • 259 3 Sum Smaller
      • 454 4Sum II
      • L609 Two Sum V
      • L587 Two Sum VI - Unique two sum pairs
      • L610 Two Sum VII - Difference equals to target
      • L382 Triangle Count
      • 532 K-diff Pairs in an Array
      • 653 Two Sum IV - Input is a BST
    • 11 backpacks
      • 474 Ones and Zeroes
      • L92 Backpack
      • L125 Backpack II
      • L440 Backpack III
      • L562 Backpack IV
      • L563 Backpack V
      • L564 Backpack VI
      • L279 Number of Ways to Represent N Cents
      • 279 Perfect Squares
      • 322 Coin Change
      • 416 Partition Equal Subset Sum
      • 377 Combination Sum IV
    • 12 graph （BFS）
      • 994 Rotting Oranges
      • 733 Flood Fill
      • 637 Average of Levels in Binary Tree
      • 1091 Shortest Path in Binary Matrix
      • 711 Number of Distinct Islands II
      • 573 Squirrel Simulation
      • 542 01 Matrix
      • 1631 Path With Minimum Effort
      • 200 Number of Islands
      • 133 Clone Graph
      • L531 Six Degrees
      • L431 Connected Component in Undirected Graph
      • L618 Search Graph nodes
      • L611 Knight Shortest Path
      • L598 Zombie in Matrix
      • 317 Shorest Distance from All Buildings
      • 127 Word Ladder
      • 126 Word Ladder II
      • L127 Topological Sort
      • 207 Course Schedule
      • 210 Course Schedule II
      • 444 Sequence Reconstruction
      • L477 Surrounded Regions
      • 269 Alien Dictionary
      • 529 Minesweeper
      • 286 Walls and Gates
      • 785 Is Graph Bipartite
      • Detect Cycle in directed graph
      • Detect Cycle in undirected graph
      • 301 Remove Invalid Parentheses
      • 419 Battleships in a Board
      • L574 Build Post Office
      • PrintShortestPath
      • 310 Minimum Height Trees
      • 695 Max Area of Island
      • 694 Number of Distinct Islands
      • 752 Open the Lock
    • 13 line sweep
      • L391 Number of Airplanes in the Sky
      • ctci 16.10 Living People
      • 370 Range Addition
      • 253 Meeting Rooms II
      • pramp mock 8
      • 554 Brick Wall
    • 14 merge sort
      • 88 Merge Sorted Array
      • L6 Merge Two Sorted Arrays
      • 23 Merge K sorted Lists
      • 21 Merge Two sorted Lists
      • L486 Merge K sorted Arrays
      • L532 Reverse Pairs
      • L408 Add Binary
      • 561 Array Partition I
    • 15 Math
      • L235 Prime Factorization
      • 492 Construct the Rectangle
      • 326 Power of Three
      • 1228 Missing Number In Arithmetic Progression
      • 775 Global and Local Inversions
      • 1551 Minimum Operations to Make Array Equal
      • 1342 Number of Steps to Reduce a Number to Zero
      • 1680 Concatenation of Consecutive Binary Numbers
      • 1037 Valid Boomerang
      • L586 Sqrt x II
      • 202 Happy Number
      • 204 Count Prime
      • 118 Pascal s Triangle
      • 119 Pascal s Triangle II
      • 396 Rotate Function
      • 766 Teoplitz Matrix
      • 89 Gray Code
      • L428 Pow x n
      • L407 Plus One
      • L408 Add Binary
      • L1 A plus B
      • 29 Divide Two Integers
      • 7 reverse Integer
      • L517 Ugly Number
      • Amicable Pair less than n
      • 179 Largest Number
      • 224 Basic Calculator
      • 227 Basic Calculator II
      • 8 String to Integer
      • 43 Multiply Strings
      • 415 Add Strings
      • 169 Majority Element
      • 229 Majority Element II
      • 171 Excel Sheet Column Number
      • 13 Roman to Integer
      • 273 Integer to English Words
      • 168 Excel Sheet Column Title
      • 311 Sparse Matrix Multiplication
      • L140 Fast Power
      • 372 Super Pow
      • 258 Add Digits
      • 12 Integer to Roman
      • 365 Water and Jug Problem
      • 9 Palindrome Number
      • 65 Valid Number
      • L180 Binary Representation
      • 561 Array Partition I
      • 384 Shuffle an Array
      • 172 Factorial Trailing Zeroes
      • 149 Max Points on a Line
      • 836 Rectangle Overlap
    • 16 two pointers - other
      • 795 Number of Subarrays with Bounded Maximum
      • 1004 Max Consecutive Ones III
      • 487 Max Consecutive Ones II
      • 1855 Maximum Distance Between a Pair of Values
      • 1089 Duplicate Zeros
      • 2511 Maximum Enemy Forts That Can Be Captured
      • 977 Squares of a Sorted Array
      • L521 Remove Duplicate Numbers in Array
      • L1870 Number of Substrings with All Zeroes
      • 1437 Check If All 1's Are at Least Length K Places Away
      • 680 Valid Palindrome II
      • 27 Remove Element
      • 26 Remove Duplicate from Sorted Array
      • 80 Remove Duplicate from Sorted Array II
      • 283 Move Zeros
      • 345 Reverse Vowels of a String
      • 28 Implement strStr
      • L387 The Smallest Difference
      • 344 Reverse String
      • 11 Container With Most Water
      • 42 Trapping Rain Water
      • 125 Valid Palindrome
      • 349 Intersection of Two Arrays
      • 350 Intersection of Two Arrays II
      • 485 Max Consecutive Ones
      • 243 Shortest Word Distance
      • 244 Shortest Word Distance II
      • 245 Shortest Word Distance III
      • Shortest Word Distance follow up
    • 17 Binary Search
      • L194 Find Words
      • 540 Single Element in a Sorted Array
      • 878 Nth Magical Number
      • 1712 Ways to Split Array Into Three Subarrays
      • 881 Boats to Save People
      • 1539 Kth Missing Positive Number
      • 744 Find Smallest Letter Greater Than Target
      • 1064 Fixed Point
      • 287 Find the Duplicate number
      • L458 Last Position of Target
      • L14 First Position of Target
      • L462 Total Occurrence of Target
      • 74 Search in a 2D Matrix
      • 240 Search in a 2D matrix II
      • 162 Find Peak Element
      • L390 Find Peak Element II
      • L74 First Bad Version
      • 374 Guess Number Higher or Lower
      • 35 Search Insert Position
      • 367 Valid Perfect Square
      • L447 Search in a Big Sorted Array
      • L459 Closest Number in Sorted Array
      • L585 maximum Number in Mountain Sequence
      • L460 K closest Numbers in Sorted Array
      • 34 Search for a Range
      • 302 Smallest Rectangle Enclosing Black Pixels
      • L437 copy books I
      • L438 copy books II
      • L141 Sqrt x
      • L183 Wood Cut
      • L254 Drop Egg
      • 410 Split Array Largest Sum
      • 274 H-Index
      • 275 H-Index II
      • RootOfNumber
      • 441 Arranging Coins
      • 875 Koko Eating Bananas
    • 18 LinkedList
      • 1721 Swapping Nodes in a Linked List
      • 234 Palindrome Linked List
      • 19 Remove Nth Node From End of List
      • 141 Linked List Cycle
      • 142 Linked List Cycle II
      • 61 Rotate List
      • 445 Add Two Numbers II
      • 206 Reverse Linked List
      • 92 Reverse Linked List II
      • 25 Reveres Nodes in K - Group
      • 2 Add Two Numbers
      • 237 Delete Node in a Linked List
      • 148 Sort List
      • 83 Remove Duplicates from Sorted List
      • 82 Remove Duplicates from Sorted List II
      • 203 Remove Linked List Elements
      • L106 Convert Sorted List to Balanced BST
      • L378 Convert Binary Search Tree to Doubly Linked List
      • 328 Odd Even Linked List
      • 23 Merge k Sorted Lists
      • 160 Intersection of Two Linked Lists
      • 138 Copy LIst with Random Pointer
      • 147 Insertion Sort List
      • 24 Swap Nodes in Pairs
      • L511 Swap Two Node in Linked List
      • 143 Reorder List
      • 369 Plus One Linked List
      • L166 Nth to Last Node in List
      • L453 Flatten Binary Tree to Linked List
      • L217 Remove Duplicate from unsorted List
      • 708 Insert into a Cyclic Sorted List
    • 19 left to right to left get best
      • L50 Product of Array Exclude itself
    • 20 finding missing
      • 448 Find All Numbers Disappeared in an Array
      • 268 Missing Number
      • 41 First Missing positive
      • L581 Longest Repeating Subsequence
    • 21 DP
      • 1235 Maximum Profit in Job Scheduling
      • 413 arithmetic Slices
      • 750 Number Of Corner Rectangles
      • 1641Count Sorted Vowel Strings
      • 1216 Valid Palindrome III
      • 120 Triangle
      • L397 Longest Increasing Continuous Subsequence
      • 64 Minimum Path Sum
      • 70 Climbing Stairs
      • L272 Climbing Stairs II
      • 62 Unique Paths
      • 63 Unique Paths II
      • L76 Longest Increasing Subsequence
      • 354 Russian Doll Envelopers
      • 368 Largest Divisible Subset
      • L116 Jump Game
      • L117 Jump Game II
      • L398 Longest Increasing Continuous Subsequence II
      • 139 Word Break
      • L108 Palindrome Partitionaing II
      • 91 Decode Ways
      • 198 House Robber
      • 213 House Robber II
      • L77 Longest Common Subsequence
      • L79 Longest Common SubString
      • 72 Edit Distance
      • 115 Distinct Subsequences
      • 276 Paint Fence
      • 403 Frog Jump
      • 44 Wildcard matching
      • 85 Maximal Rectangle
      • 312 Burst Ballons
      • 517 Super Washing Machines
      • 152 Maximum Product Subarray
      • 97 Interleaving String
      • L581 Longest Repeating Subsequence
      • 10 Regular Expression Matching
      • 221 Maximal Square
      • 264 Ugly Number II
      • L394 Coins in Line
      • L395 Coins in Line II
      • L396 Coins in line III
      • 87 Scramble String
      • L476 Stone Game
      • L593 Stone Game II
      • L43 Maximum Subarray III
      • 256 Paint House
      • 361 Bomb Enemy
      • L584 Drop Eggs II
      • meeting room 3
      • 392 Is Subsequence
      • 334 Increasing Triplet Subsequence
      • 494 Target Sum
      • 265 Paint House II
      • 174 Dungeon Game
    • 22 Data Structure (stack & queue --“dek”)
      • 1249 Minimum Remove to Make Valid Parentheses
      • 225 Implement Stack using Queues
      • L362 Sliding Window Maximum
      • 439 Ternary Expression Parser
      • 20 Valid Parentheses
      • 155 Min Stack
      • 150 Evaluate Reverse Polish Notation
      • L495 Implement Stack
      • L492 Implement Queue by Linked LIst
      • L493 Implement Queue by Linked List II
      • 232 Implement Queue using Stacks
      • L229 Stack Sorting
      • L224 Implements Three Stacks by Singly Array
      • 71 Simplify Path
      • 32 Longest Valid Parentheses
      • 379 Design Phone Directory
      • L643 Longest Absolute File Path (388)
      • 716 Max Stack
      • 609 Find Duplicate File in System
    • 23 Heap
      • 1337 The K Weakest Rows in a Matrix
      • 1675 Minimize Deviation in Array
      • 1329 Sort the Matrix Diagonally
      • 407 Trapping Rain Water II
      • L81 Data Stream Median
      • L360 Sliding Window Median
      • L130 Hepify
      • 378 Kth Smallest Element in a Sorted Matrix
      • L465 Kth Smallest Sum In Two Sorted Arrays
      • L471 Top K Frequent Words
      • 347 Top K Frequent Elements
      • L131 Building Outline
      • 218 The Skyline Problem
      • 373 Find K Pairs with Smallest Sums
      • 703 Kth Largest Element in a Stream
      • 692 Top K Frequent Words
      • 743 Network Delay Time
    • 24 Union Find (Disjoint Set)
      • L589 Connecting Graph
      • L590 Connecting Graph II
      • L591 Connecting Graph III
      • L137 Graph Valid Tree
      • L432 Find Weak Connected Component in the Directed Graph
      • 305 Number of Island II
      • L629 Minimum Spanning Tree
      • 547 Friend Circles
    • 25 Trie and N-ary Tree
      • 1506 Find Root of N-Ary Tree
      • L559 Trie Service
      • L442 Implement Trie
      • L527 Trie Serialization
      • L473 Add and Search Word
      • L132 Word Search II
    • 26 Tree
      • 1257 Smallest Common Region
      • 617 Merge Two Binary Trees
      • L628 Maximum Subtree
      • 1022 Sum of Root To Leaf Binary Numbers
      • 623 Add One Row to Tree
      • 1245 Tree Diameter
      • 690 Employee Importance
      • 1379 Find a Corresponding Node of a Binary Tree in a Clone of That Tree
      • 938 Range Sum of BST
      • 222 Count Complete Tree Nodes
      • L467 Complete Binary Tree
      • 173 Binary Search Tree Iterator
      • 230 Kth Smallest Element in a BST
      • 100 Same Tree
      • L470 Tweaked identical Binary Tree
      • 101 Symmetric Tree
      • 98 Valid Binary Search Tree
      • 255 Verify Preorder Sequence in BST
      • 226 Invert Binary Tree
      • 110 Balanced Binary Tree
      • 99 Recover Binary Search Tree
      • 156 Binary Tree Upside Down
      • 102 Binary Tree Level Order Traversal
      • 107 Binary Tree Level Order Traversal II
      • 103 Binary Tree Zigzag Level Order Traversal
      • L242 Convert Binary Tree to Linked Lists by Depth
      • 104 Maximum Depth of Binary Tree
      • L155 Minimum Depth of Binary Tree
      • 235 Lowest Common Ancestor of a BST
      • 236 Lowest Common Ancestor of a Binary Tree
      • L474 Lowest Common Ancestor II
      • L578 Lowest Common Ancestor III
      • 297 Serialize and Deserialize Binary Tree
      • 270 Closest Binary Search Tree Value
      • 257 Binary Tree Paths
      • 366 Find Leaves of Binary Tree
      • L11 Search Range in Binary Search Tree
      • 199 Binary Tree Right Side View
      • 116 Populating Next Right Pointers in Each Node
      • 108 Convert Sorted Array to Binary Search Tree
      • 449 Serialize and Deserialize BST
      • L126 Max Tree
      • L472 Binary Tree Path Sum III
      • L246 Binary Tree Path Sum II
      • 112 Path Sum
      • 113 Path Sum II
      • 437 Path Sum III
      • 129 Sum Root to Leaf Numbers
      • L475 Binary Tree Maximum Path Sum II
      • L94 Binary Tree Maximum Path Sum
      • 298 Binary Tree Longest Consecutive Sequence
      • L614 Binary Tree Longest Consecutive Sequence II
      • L619 Binary Tree Longest Consecutive Sequence III
      • 117 Populating Next Right Pointers in Each Node II
      • 404 Sum of Left Leaves
      • L597 Subtree with Maximum Average
      • L596 minimum Subtree
      • 501 Find Mode in Binary Search Tree
      • 333 Largest BST Subtree
      • 508 Most Frequent Subtree Sum
      • 250 Count Univalue Subtrees
      • 513 Find Bottom Left Tree Value
      • 515 Find Largest Value in Each Tree Row
      • L245 Subtree
      • L375 Clone Binary Tree
      • 337 House Robber III
      • 96 Unique Binary Search Tree
      • 538 Convert BST to Greater Tree
      • 536 Construct Binary Tree from String
      • Serilization and Deserialize n-ary Tree
      • 543 Diameter of Binary Tree
      • 105 Construct Binary Tree from Preorder and Inorder Traversal
      • 106 Construct Binary Tree form Inorder and Postorder Traversal
      • 652 Find Duplicate Subtrees
      • 285 Inorder Successor in BST
      • 450 Delete Node in a BST
      • 272 Closest Binary Search Tree Value II
      • 671 Second Minimum Node In a Binary Tree
      • 814 Binary Tree Pruning
      • 669 Trim a Binary Search Tree
      • 95 Unique Binary Search Trees II
      • 510 Inorder Successor in BST II
      • 545 Boundary of Binary Tree
      • 563 Binary Tree Tilt
      • 582 Kill Process
    • 27 Segment Tree or BIT
      • Segment Tree
      • Binary Index Tree （Fenwick Tree）
      • 315 Count of Smaller Numbers After Self
      • 493 Reverse Pairs
      • 1649 Create Sorted Array through Instructions
      • 308 Range Sum Query 2D - Mutable
      • 307 Range Sum Query - Mutable
    • 28 Hash Table or Set
      • 2395 Find Subarrays With Equal Sum
      • 760 Find Anagram Mappings
      • 389 Find the Difference
      • 1198 Find Smallest Common Element in All Rows
      • 1394 Find Lucky Integer in an Array
      • 1133 Largest Unique Number
      • 1461 Check If a String Contains All Binary Codes of Size K
      • 575 Distribute Candies
      • 1165 Single-Row Keyboard
      • 709 To Lower Case
      • 987 Vertical Order Traversal of a Binary Tree
      • 1657 Determine if Two Strings Are Close
      • 1640 Check Array Formation Through Concatenation
      • L389 Valid Sudoku
      • 314 Binary Tree Vertical Order Traversal
      • 49 Group Anagrams
      • 242 Valid Anagram
      • 451 Sort Characters By Frequency
      • L129 Rehashing
      • L128 Hash Function
      • 205 Isomorphic Strings
      • 290 Word Pattern
      • 128 Longest Consecutive Sequence
      • 249 Group Shifted Strings
      • 383 Ransom Note
      • 358 Rearrange String k Distance Apart
      • 525 Contiguous Array
      • 187 Repeated DNA Sequences
      • Rearrange chars in string such that no 2 adjacent are the same
      • 217 Contains Duplicate
      • 219 Contains Duplicate II
      • 220 Contains Duplicate III
      • 599 Minimum Index Sum of Two Lists
      • 387 First Unique Character in a String
      • 771 Jewels and Stones
      • 767 Reorganize String
      • 819 Most Common Word
      • Pramp - Getting a Different Number
    • 29 Search(dfs) and BackTrack
      • 37 Sudoku solver
      • 51 N_Queens
      • 52 N_Queens II
      • 140 Word Break II
      • 131 Palindrome Partitioning
      • 79 Word Search
      • 351 Android Unlock Patterns
      • 291 Word Pttern II
      • 211 Add and Search Word - Data structure Design
      • 22 Generate Parentheses
      • 93 Restore IP Addresses
      • 282 Expression Add Operators
      • 425 Word Squares
      • 698 Partition to K Equal Sum Subsets
    • 30 DFS (recursion)
      • L22 Flatten List
      • L601 Flatten 2D Vector
      • L528 Flatten Nested List Iterator
      • 339 Nested List Weight Sum
      • 364 Nested List Weight Sum II
      • 394 Decode String
      • 385 Mini Parser
      • 430 Flatten a Multilevel Doubly Linked List
    • 31 Bit Manipulation
      • 751 IP to CIDR
      • 1310 XOR Queries of a Subarray
      • 477 Total Hamming Distance
      • 461 Hamming Distance
      • 191 Number of 1 bits
      • 231 Power of Two
      • 136 Single Number
      • 137 Single Number II
      • 260 Single Number III
      • L824 Single Number IV
    • 32 String
      • 58 Length of Last Word
      • 806 Number of Lines To Write String
      • 953 Verifying an Alien Dictionary
      • 1704 Determine if String Halves Are Alike
      • 524 Longest Word in Dictionary through Deleting
      • 821 Shortest Distance to a Character
      • 1662 Check If Two String Arrays are Equivalent
      • 468 Validate IP Address
      • 6 ZigZag Conversion
      • 14 Longest Common Prefix
      • L637 Valid Word Abbreviation
      • 527 Word Abbreviation
      • L659 Encode and Decode Strings
      • 288 Unique Word Abbreviation
      • 443 String Compression & ctci189 1 point 6 String Compression
    • 33 单调栈
      • 1673 Find the Most Competitive Subsequence
      • 84 Largest Rectangle in Histogram
      • 402 Remove K Digits
      • 316 Remove Duplicate Letters
      • 739 Daily Temperatures
    • 34 贪心 Greedy
      • 1005 Maximize Sum Of Array After K Negations
      • 452 Minimum Number of Arrows to Burst Ballons
      • 946 Validate Stack Sequences
      • 134 Gas Station
      • 1663 Smallest String With A Given Numeric Value
    • 35 Arrays
      • 1887 Reduction Operations to Make the Array Elements Equal
    • other
      • hankerrank Data Updates
      • 755 Pour Water
      • 1304 Find N Unique Integers Sum up to Zero
      • 1118 Number of Days in a Month
      • 284 Peeking Iterator
      • 594 Longest Harmonious Subsequence
      • 1629 Slowest Key
      • 985 Sum of Even Numbers After Queries
      • 1646 Get Maximum in Generated Array
      • 667 Beautiful Arrangement II
      • 277 Find the Celebrity
      • L540 Zigzag Iterator
      • L541Zigzag Iterator II
      • 289 Game of Life
      • 161 One Edit Distance
      • 459 Repeated Substring Pattern
      • 38 Count and Say
      • 4 Median of Two Sorted Arrays
      • 157 Read N Characters Given Read4
      • 158 Read N Characters Given Read4 II - Call multiple times
      • 398 Random Pick Index
      • 68 Text Justification
      • 165 Compare Version Numbers
      • 412 fizz buzz
      • 605 Can Place Flowers
      • 796 Rotate String
        • Find Median in super big array
    • Design
      • L134 LRU
      • 355 Design Twitter
      • 460 LFU
      • 380 Insert Delete GetRandom O 1
      • 381 Insert Delete GetRandom O 1 Duplicates allowed
      • 535 Encode and Decode TinyURL
      • L234 Webpage Crawler
      • L231 Typeahead
      • L555 Counting Bloom Filter
      • L556 Standard Bloom filter
      • 432 All O one Data Structure
      • L215 Rate Limiter
      • 359 Logger Rate Limiter
      • 362 Design Hit Counter
      • 348 Design Tic-Tac-Toe
      • L529 GeoHash
      • L530 Geohash II
      • L526 Load Balancer
      • 707 Design Linked List
      • 622 Design Circular Queue
      • 794 Valid Tic-Tac-Toe State
    • 面经
      • 对角线打印矩阵
      • edit distance to palindrome
      • Equilibrium index of an array
      • BigInt sub
      • xml parser
      • Weighted ramdom sampling
      • csv parser
      • password generate according to list
      • Forward backward slash sperated squares
      • gift wrapping algorithm
      • file access
  • 公司
    • Time line
    • Amazon 2017-04
    • Snapchat 2017-04
    • Uber 2017 -06
    • Facebook 2017-06
    • Microsoft 2017-07
    • LinkedIn 2019 -01
    • Micorsoft 2019-02
    • JPMorgan 2019-02
    • Cisco 2019-02
    • Dropbox 2019-02
    • Yahoo 2019-02
    • VMware 2019-02
    • Airbnb 2019-02
    • TikTok
  • Templates
    • 1 Sorting模板
    • 2 2分template
    • 3 树的模板
    • 4 链表基础模板
    • 5 去重基本方法
    • 6 其他常用snipets
    • 8 clarify questions
    • 9 Bit Manipulation 常用公式
    • 10 Common Complexities
    • 11 OOD
    • 12 System Design
      • Grokking Modern System Design Interview notes
        • 关于怎么prepare
      • 关于db
      • 关于estimation
      • General Concepts
        • 其他有待展开
        • Reactive pattern（Reactive Spring）
        • GraphQL
        • Config Management
        • Observability
          • 关于tracing
        • OpenApi - swagger
        • Service Mesh
      • 具体系统
        • Delay Schedule
        • 倒排索引
        • Rate limiter + Datadog
        • Bloom Filter + Count-min sketch
        • Distributed DB bigtable
        • Distributed File System(HDFS/GFS)
        • web crawler
        • TinyURL
        • 设计linkedIn显示几度关系
        • News feed
        • 用户系统设计
        • 设计Memcache + 少少redis相关信息
        • 设计whatsapp chatting
        • typeahead
    • 13 Testing
    • 14 other notes
    • 15 常用数学运算
    • 16 Other stuffs
    • 17 Questions to company
    • 18 Restful Webservices
    • 19 Network stuff
    • 20 Behavior Questions
    • 21 Java 语法注意点
      • String
Powered by GitBook
On this page

Was this helpful?

  1. My Notes

7 Subarrays (prefix sum)

这类题用到prefix sum。感觉sliding window求size，subarrays求sum/具体下标。

prefix的array/matrix留空前面一个格子/一行一列来算比较方便，用的时候把j +1减去 i 就好了。

6年后发现，还有一类是用hashmap来算prefix/suffix的

基础题：

303 Range Sum Query - immutable -- prefixSum

304 Range Sum Query 2D - immutable -- prefix Sum

L558 Sliding Window Matrix Maximum

1310 XOR Queries of a Subarray -- 套着xor皮的prefix sum

528 Random Pick with Weight

Max/Min :

L41 Maximum Subarray(53) -- L402求下标

L42 Maximum Subarray II

L44 Minimum Subarray

L45 Maximum Subarray Difference

L620 Maximum Subarray IV

L621 Maximum Subarray V

L617 Maximum Average Subarray (2分，留意2分讲座笔记）

523 Continuous Subarray Sum -- 感觉有点2分的意味，有空看看

Stock1 Stock 3 都有点prefix Sum

首尾链接：

L403 Continuous Subarray Sum II -- 有环

L402 Continuous Subarray Sum -- L41求max值，这里求具体下标。

DP：

L43 Maximum Subarray III (DP -- 划分类)

L191 Maximum product Subarrays (DP) （152）

Stock 3（DP -- 划分类）

hash or 2分：-- 有点像在用hashmap做dp的感觉

L138 Subarray Sum -- hash

L405 Submatrix Sum --L138进化版

L404 Subarray Sum II -- 用2分优化

325 Maximum Size Subarray Sum Equals k -- 感觉又是一个L138的变种

L139 Subarray Sum Closest

523 Continuous Subarray Sum -- L138又变，这次来个mod

525 Contiguous Array -- 又一个L138

1477 Find Two Non-overlapping Sub-arrays Each With Target Sum

560 Subarray Sum Equals K

变体or相关：

437 Path Sum III

other related：

713 Subarray Product Less Than K

724 Find Pivot Index -- 某次contest的题

308 Range Sum Query 2D - Mutable -- segment tree or BIT

307 Range Sum Query - Mutable -- segment tree or BIT

L643 Longest Absolute File Path (388) -- 实现上可以用prefix sum数组或者stack

PreviousL185 Matrix Zigzag TraversalNext560 Subarray Sum Equals K

Last updated 1 year ago

Was this helpful?