Linear Data Structure Summary
0. Enumeration method
对于 双变量问题，例如两数之和 a+b = t, 可以枚举b右侧的数，同时维护&查找左侧枚举过的元素有没有a=t-b。这可以用哈希表维护&记录每一个枚举过的数和该数的位置。这种方法叫“枚举右，维护左”
枚举右，维护左
枚举中间
1. presum
classic prefix sum
理解前缀和定义：对于nums数组，presum[i] = presum[i-1]+nums[i-1], presum[0]=0, presum[1]=presum[0]+nums[0]....
子数组的元素和可以转化成两个前缀和的差: sum of array i~j = presum[i]-presum[j], sum of array 0~j = presum[j]-presum[0]
presum+hashmap
通常需要 枚举右，维护左 的技巧
- 560. Subarray Sum Equals K 概念讲解
- 930. Binary Subarrays With Sum
- 523. Continuous Subarray Sum 讲解
- 437. Path Sum III 讲解
- 525. Contiguous Array 讲解
二维前缀和
2. 差分数组 difference array
3. 栈 stack
基础原理
临项消除
- 2696. Minimum String Length After Removing Substrings
- 1047. Remove All Adjacent Duplicates In String
- 1544. Make The String Great
- 735. Asteroid Collision
表达式解析
利用stack实现“先计算乘除，后计算加减”，来计算一个表达式
- 1006. Clumsy Factorial
- 150. Evaluate Reverse Polish Notation
- 227. Basic Calculator II
- 394. Decode String
合法括号字符串
用stack，遇到左括号就加入，遇到右括号就尝试pop&消除
- 20. Valid Parentheses
- 921. Minimum Add to Make Parentheses Valid
- 856. Score of Parentheses
- 678. Valid Parenthesis String
- 1190. Reverse Substrings Between Each Pair of Parentheses
- 1021. Remove Outermost Parentheses