Arrays Overview
Arrays Overview
Sum
主要就是Hash table 和 two pointers的应用。一句话概括就是准确值用HashMap，接近值就是先sort 再 Two Points
- Two Sum
- Two Sum II
- Two Sum III
- Two Sum IV
- Two Sum Less Than K
- 考虑点在于有没有O(n)的算法
- 排序 + two pointers， 排序部分如果最大值很小可以用bucket sort
- Three Sum
- 去重关注一下
- Three Sum Closest
- Three Sum Smaller
- 这个问题告诉我们排序 + two pointers 来寻找target的方法的成立条件是binary search, 它实际上并没有遍历所有可能性
- 但是我们要求的是triplet的个数，所以用这个方法也成立，只要改一下加rst的条件
- 3Sum With Multiplicity
- Valid Triangle Number
高精度计算类
这类问题主要找一种自己习惯的写法或者说模板，如果是结合链表，注意一下判断该点是否存在的细节。 对于高精度乘法时，首先结果的位数很容易证明为n+m，因为假设都是9的极端情况即可。相乘时对应的index（i + j & i + j + 1）
Binary Search
Details may be found HERE.
Top K
Details may be found HERE.
Subarray
- Maximum Subarray
- Subarray Sum Equals K
- Maximum Product Subarray
- Subarray Sums Divisible by K
- Minimum Size Subarray Sum
- Maximum Size Subarray Sum Equals k
- Subarray Product Less Than K
- Maximum Sum of Two Non-Overlapping Subarrays
- Continuous Subarray Sum
- Maximum Length of Repeated Subarray
- Sum of Subarray Minimums
- Shortest Unsorted Continuous Subarray
Maximum Subarray 由于是任意的subarray，所以自由度很高，方便贪心。到Subarray Sum Equals K 时使用HashMap来记录总的sum，再由sum - k 是否在HashMap中来看sum(i) - sum(j) 是否等于K，其实算cumulative sum。
Subarray Sums Divisible by K也可以使用HashMap解决，改用sum % K作为Key即可，不过有一点值得注意，sum % K存在负数情况，所以要加上K改为正数。当然也可以使用大小为K的Array来代替HashMap来加速。
Minimum Size Subarray Sum 该问题的O(n)解法用two pointer（sliding window）即可；本题还有O(nlogn)的解法，结合了Binary Search 和 sliding window。
Maximum Sum of Two Non-Overlapping Subarrays 本质上还是sliding window的应用，
Maximum Length of Repeated Subarray 算DP题
Sorted Array
Others
- Remove Duplicates from Sorted List
- Minimum Cost to Connect Sticks
- Top K Frequent Words
- Find Median from Data Stream
- Top K Frequent Elements
- Word Ladder
- Happy Number
- Trapping Rain Water
- Rotate Image
- Best Time to Buy and Sell Stock
- Word Ladder II
- Max Area of Island
- Merge Sorted Array
- Start from the end for no extra space and one pass requirement
- Squares of a Sorted Array
- Sort Transformed Array
- Partition Array into Disjoint Intervals