## $O(n)$ 找出数组中特殊的数

• LeetCode 搜 Single Number

### 数组中只有一个数出现1次，其他数都出现了3次

one 存的是出现一次的位，如果这一位出现两次，那么只能为0 ((1+2)%3)
two 存的是出现两次的位，如果这一位出现一次，那么只能为0 ((2+1)%3)

## 股票问题

• LeetCode 搜 Majority Element
• 参考

### 能买入卖出多次，有冻结期k (即卖k天出后才能买入)

d[i] = max(cur+a[i],d[i-1])
cur = max(cur,d[i-k]-a[i])

## 寻找数组中的多数元素

• LeetCode 搜 Majority Element

Boyer-Moore Majority Vote algorithm可以做到 时间 O(n) 空间 O(1)

## K-Sum

### 3Sum

#### 转化为2Sum

j,k 用 2Sum 的头尾指针的方法，保证 i < j < k

### KSum

#### 理论最优

k-SUM can be solved more quickly as follows.

For even k: Compute a sorted list S of all sums of k/2 input elements. Check whether Scontains both some number x and its negation −x. The algorithm runs in O(n^(k/2)logn) time.

For odd k: Compute the sorted list S of all sums of (k−1)/2 input elements. For each input element a, check whether S contains both x and a−x, for some number x. (The second step is essentially the O(n^2)-time algorithm for 3SUM.) The algorithm runs in O(n^((k+1)/2)) time.

Both algorithms are optimal (except possibly for the log factor when k is even and bigger than 2) for any constant k in a certain weak but natural restriction of the linear decision tree model of computation.

## Rotated Sorted Array

• LeetCode 搜 Rotated

### Find Minimum in Rotated Sorted Array

#### 含重复元素

nums[m] == nums[r]时，r = r - 1，即缩小这个区间