前缀和
- 53 Maximum Subarray 找和最大子数组（找最小的话 元素取反求最大就行）
- 从前向后 计算sum同时 维持最小的前缀和
- dp dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); dp[i]是已i元素结尾的子数组最大和
- lt138 Subarray Sum 找一个和为零的子数组 转化为找两个前缀和相同的子数组 中间的数和为零；注意要put(0, -1)
- lt139 Subarray Sum Closest 找一个和最接近零的子数组 转化为找两个前缀和最接近的子数组;注意要添加Pair[0, 0] 计算下表0-2子数组和 用到presum[2]-presum[-1]
- Prefix Sum + Sort (Offline Algorithm)
Find the subarray sum closet to 0 => find two prefix sum closet to each other => find min difference in sorted prefix sum array
Sort (prefixSum, index) pair
Time Complexity: O(nlogn) - 另一种解法
Prefix Sum + TreeMap (Online Algorithm)
Key: prefix sum Value: index
TreeMap is implemented using Red Black Tree (Balanced BST), can be used to find the closet element Ceiling/Floor
Time Complexity: O(nlogn)
todo
- Subarray Sum Equals K
- Continuous Subarray Sum
- Prefix Sum + Sort (Offline Algorithm)
interval
- 57 Insert Interval 已经按start排好序 插入新的interval
- inplace
- 新建一个
- lt839 Merge Two Sorted Interval Lists merge两个按start排好序的interval list - inplace
- 新建一个
- lt577 Merge K Sorted Interval Lists
todo
56 Merge Intervals
252 Meeting Rooms
253 Meeting Rooms II
merge
- lt464 Sort O(nlogn) merge sort/quick sort
- 23 Merge k Sorted Lists merge/heap
- lt486. Merge K Sorted Arrays 同上用heap
10.5. 外排序与K路归并算法 大文件排序 拆成小文件 小文件排序 + k路并归 - lt577 Merge K Sorted Interval Lists
12 88 Merge Sorted Array 两个排好序的数组 把小的数组merge到大的数组里（空间足够）
13 lt839 Merge Two Sorted Interval Lists merge两个按start排好序的interval list
14 311 Sparse Matrix Multiplication 提取稀疏矩阵中信息 转化成dense
杂题
- 4 Median of Two Sorted Arrays
- 利用findkth k->k-k/2
- 二分答案
- 349 Intersection of Two Arrays hash/two pointer
- 350 Intersection of Two Arrays II
