文章目录
小总结
数组类题目，涉及到数组中两个数的关系（如求和，他们之间数的和等），可以考虑双指针法，但双指针的话不要局限在两层for循环这个死板的的认知上。还有诸如移动窗口以及left、right指针向中间靠拢这些变体。
1、旋转矩阵
题目
分析
解法1
本题的重点在于能否发现点在旋转前后的关系，假如旋转点是（i，j），可以想象，旋转后的行就是旋转前的列，而旋转后列同旋转前的行关于中心对称，即是（j，n-i-1）；
第二点如上面两副图所示，整个矩阵的旋转可以理解为起点都在左上角区域，然后依次顺时针移动。如上左图，区域1转到了区域2,2转到3,3转回1。（还要注意奇偶的差别）
因此整个变换可分解为按区域的三次互换：
①swap(matrix[i][j], matrix[j][n-i-1]);
②swap(matrix[i][j], matrix[n-i-1][n-j-1]);
③swap(matrix[i][j], matrix[n-j-1][i]);
解法2
此题还可以通过翻转整个数组,再按正对角线交换两边的数来解答，如下图：
扩展
这里不讨论下逆时针旋转90度是失职的，第一种解法不必说，观察即可，对于第二种方法。
第一步的交换不变，第二步交换要按逆对角线来做。亲测正确。
复杂度
我参考的那位仁兄给的如下：
时间复杂度为O(n^2)；
空间复杂度为O(1)；
注：这里的n是指边长
2、三数之和
题目
分析
这题的解法就是排序后使用三指针，这里主要说下对于避免重复的处理方式，就是在指针前进时，如果遇到和上一个指向的数相同的数就跳过，这样既可避免重复。
//下面两个查重只需要留一个，这里好好品味下缘由
if(left>start+1&&nums[left]==nums[left-1]){
++left;
continue;
}
if(right<n-1&&nums[right]==nums[right+1]){
--right;
continue;
}
在第一个指针位置确定后，left和right就分别指向它右边区域的两端，并向中央逼近。但这里在查重的时候并不需要将left和right都进行检查，因为一旦遇到和等于0的组合后，会同时执行“++left” 和“–right”。而只要这两者中有一个没有重复，那么整体就不会重复。
复杂度
时间复杂度：O(n^2)
空间复杂度：O（1）
3、下一个排列
题目
分析
这题咋一看好像很简单，从后往前找到顺序的两数互换位置就行了，但实际上，这只是第一步……
我们应该再往后找比两数中大的最小的数，再来还要将后面的数顺序颠倒。
以“123465” 为例：首先找到顺序两数4和6，然后按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列.
解题步骤如下：
①从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序。
②在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。
③将 A[i] 与 A[k] 交换。
④可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序。
⑤如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4。
代码如下：
void nextPermutation(vector<int>& nums) {
int n=nums.size();
int i=n-2;
for(;i>=0;--i){
if(nums[i]<nums[i+1]) break;
}
if(i<0){
reverse(nums.begin(),nums.end());
}
else{
for(int j=n-1;j>i;--j){
if(nums[j]>nums[i]){
swap(nums[i],nums[j]);
break;
}
}
reverse(nums.begin()+i+1,nums.end());
}
}
注意如果出现 i<0 的情况，则说明nums是降序或者全是相等的数，这时统一将数组整个翻转即可。
复杂度
时间复杂度：O(N）
空间复杂度：O(1)
4、盛最多水的容器和数对和
题目
分析
这两题依旧是使用了双指针，但和之前的不同，这里是要维护一个left和right指针分别从左右开始往中间遍历，同时数对和这题需要进行排序。如第11题：
while(left<right){
area=max(area,min(height[left],height[right])*(right-left));
if(height[left]>height[right]) --right;
else if(height[left]<height[right]) ++left;
else{
++left;
--right;
}
}
这里其实用到了贪心思想，即总是移动矮的那个指针。
复杂度
时间复杂度：O（N）
空间复杂度：O（1）
5、删除排序数组中的重复项
题目
分析
这里用到了双指针的一种变体，一开始两个指针指向初始位置，如果left和right的值相等，就++right，直到不等为止。然后先将right的值赋值给left+1，然后++right。如下：
while(right<n){
if(nums[left]==nums[right]) ++right;
else{
nums[++left]=nums[right++];
}
}
注意：因为一开始left和right指向同一位置，所以第一次循环中肯定是会++right。
复杂度
时间复杂度：O（N）
空间复杂度：O（1）
6、合并区间
题目
分析
这题其实就是按“看起来”的方法做就可以了，即：
1、首先按区间的第一个数字排序，关于这一点，STL的sort也可做到。
2、比较排序后区间进行合并。
这里合并的方式可以按如下进行，先将第一个区间放进输出的容器out中，然后循环比较当前区间和out中的尾部区间，并更新out的尾部或将当前区间放进out中，如下：
vector<vector<int>> out;
out.push_back(intervals[0]);
for(int i=0;i<n;++i){
if(intervals[i][1]<out.back()[1]) continue;
else if(intervals[i][0]<=out.back()[1]){
out.back()[1]=intervals[i][1];
}
else{
out.push_back(intervals[i]);
}
}
注意这里back()函数的使用。
复杂度
时间复杂度：O（N）
空间复杂度：O（N）
7、移动零
题目
分析
方法一：
维护一个count记录遇到的0的个数，然后将数组遍历一遍，把不等于0的数 i 移动到第 i-count 位，如下：
int count=0;
for(int i=0;i<n;++i){
if(nums[i]==0) ++count;
else if(count){
nums[i-count]=nums[i];
}
}
然后把后count个数全部置0。
方法二：
运用快排的思想，以0为参考数，将不等于0的数置换到左边，而等于0的数放在右边，如下：
int j=0;
for(int i=0;i<n;++i){
if(nums[i]!=0){
swap(nums[i],nums[j++]);
}
}
注：这里的 j 永远指向第一个 0（如果有的话）。
复杂度
时间复杂度：O（N）
空间复杂度：O（1）
8、x的平方根&两数相除
题目
分析
x的平方根
这题使用二分法查找，如下：
long left=0,right=x/2+1;
while(left<right){
long mid=left+((right-left+1)>>1);
long square=mid*mid;
if(square>x) right=mid-1;
else left=mid;
}
这里 right 的取值基于大于4的数的一半的平方一定大于它本身。同时令 right=x/2+1 以应对 1 的情况。
两数相除
这里先对被除数进行处理，主要是处理几种特殊情况，然后把正负的问题搞定，如下：
int divide(int dividend, int divisor) {
if(dividend==0) return 0;
if(divisor==1) return dividend;
if(divisor==-1){
return dividend<=INT_MIN?INT_MAX:-dividend;
}
int sym=1;
long a=dividend,b=divisor;
if((a>0&&b<0)||(a<0&&b>0)) sym=-1;
if(a<0) a=-a;
if(b<0) b=-b;
int ret=div(a,b);
if(sym==1) return ret;
return -ret;
}
这里为防止越界，需要把 int 换成 long。
div函数进行递归，让b指数增长，直到大于a，这时得到刚好小于a的值，tb，然后让 a=a-tb，进入下一次递归，直到a<b，同时维护一个数count，用来记录用了多少个b，如下：
int div(long a,long b){
if(a<b) return 0;
int count=1;
long tb=b;
while((tb+tb)<=a){
tb+=tb;
count+=count;
}
return count+div(a-tb,b);
}
复杂度
时间复杂度：O（lgN）
空间复杂度：O（1）
9、和为K的子数组
题目
分析
方法一：暴力双指针
先用一个指针left固定左边界，然后用一个right指针遍历右边。
时间复杂度：O(N^2)
方法二：前缀和+哈希优化
所谓前缀和就是用数组把前 i 个数的和记录下来。
这里的暴力做法和法一一样，left固定左边界，right向右遍历，记录两个位置的前缀和之差等于 k 的节点。
哈希优化就是用map记录下前缀和及它出现的次数，然后用一个 sum 值记录当前的前缀和，然后在map中寻找是否存在 sum-k 的前缀和及它的个数是多少，代码如下：
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> um;
um[0]=1;
int sum=0;
int count=0;
for(int a:nums){
sum+=a;
if(um.count(sum-k)) count+=um[sum-k];
++um[sum];
}
return count;
}
复杂度
时间复杂度：O(N)
空间复杂度：O(N)
10、毒蘑菇（ZJ）
题目
分析
这里用到了贪心的思想，无视所有的有毒蘑菇，而一旦遇到食用蘑菇就将其加到体力上，代码如下：
bool mushroom(vector<int> &nums,int k){
int n=nums.size();
int life=k;
for(int i=0;i<n;++i){
if(nums[i]>0) life+=nums[i];
--life;
if(life==0) return false;
}
return true;
}
复杂度
时间复杂度：O(N)
空间复杂度：O(1)
11、1~n整数中1出现的次数
题目
分析
参考：
link
将 1 ~ n 的个位、十位、百位、…的 1 出现次数相加，即为 1 出现的总次数。
计算方法：
1.当cur=0时：此位1的出现次数只由高位high决定，计算公式为：high*digit
2.当cur=1时：此位1的出现次数由高位high和低位low决定，计算公式为：high*digit+low+1
3.其他情况，此位1的出现次数只由高位high决定计算公式为：（high+1）*digit
注：情况2中“+1”是因为还有low位全为0时的这种情况。情况3中的“+1”是因为还有他自身为1这一种情况。
复杂度
时间复杂度：O(1)
空间复杂度：O(1)
12、跳跃游戏I&II
题目
分析
这两题本质上都用了贪心思想。
跳跃游戏：
这里的思路是在遍历时记录能跳的最远的位置，如果当前位置大于最远位置就返回false，否则返回true，代码如下：
bool canJump(vector<int>& nums) {
int n=nums.size();
//count记录能到达的最远距离
int count=0;
for(int i=0;i<n;++i){
if(count<i) return false;
count=max(count,i+nums[i]);
}
return true;
}
复杂度
时间复杂度：O(N)
空间复杂度：O(1)
跳跃游戏II：
这题和上题的思路是一样的，即尽量往远了跳。但是这题的目光要更长远一些，我们这一步要往下一步能跳的更远的位置跳，代码如下：
int jump(vector<int>& nums) {
int n=nums.size();
if(n<2) return 0;
int i=0,step=0;
while(i<n){
//记录这一步加下一步一起能跳的最远的值
int maxstep=0;
int pos=0;
++step;
for(int j=1;j<=nums[i];++j){
if(i+j>=n-1) return step;
if(i+j+nums[i+j]>maxstep){
maxstep=i+j+nums[i+j];
pos=i+j;
}
}
i=pos;
}
return step;
}
复杂度
时间复杂度：O(M*N) 其中M为能跳的步数的平均值
空间复杂度：O(1)
13、螺旋矩阵
题目
分析
参考：
link
这里的思路很朴素，但充满了闪光点，即维护四个数来分别记录矩阵的上下左右边界，并在每记录完一行或者一列后将这四个数刷新。
停止条件：上下或者左右边界交错。
代码如下：
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int row=matrix.size();
if(row==0) return {};
int col=matrix[0].size();
int a = 0, b = col - 1, c = 0, d = row - 1;
vector<int> ret;
while(true){
for(int i=a;i<=b;++i) ret.push_back(matrix[c][i]);
if(++c>d) break;
for(int i=c;i<=d;++i) ret.push_back(matrix[i][b]);
if(--b<a) break;
for(int i=b;i>=a;--i) ret.push_back(matrix[d][i]);
if(--d<c) break;
for(int i=d;i>=c;--i) ret.push_back(matrix[i][a]);
if(++a>b) break;
}
return ret;
}
复杂度
时间复杂度：O(M
N) 其中M,N分别表示矩阵的长宽
空间复杂度：O(M
N)
14、数据流中的中位数
题目
分析
参考：
link
这里要准备一个大顶堆和一个小顶堆，每个堆中装数据流中一半的数，同时，大顶堆中装较小的数，小顶堆中装较大的数。然后中位数可以直接由两个堆的顶得出，如下：
这里的难点集中在把数加入到堆中这一步上，代码如下：
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {
size=0;
}
void addNum(int num) {
if(big.empty()) big.push(num);
else if(size%2){
if(num>big.top()){
small.push(big.top());
big.pop();
big.push(num);
}
else small.push(num);
}
else{
if(!small.empty()&&num<small.top()){
big.push(small.top());
small.pop();
small.push(num);
}
else big.push(num);
}
++size;
}
double findMedian() {
if(size%2) return big.top();
else return (big.top()+small.top())/2;
}
private:
priority_queue<double,vector<double>,greater<double>> big;
priority_queue<double,vector<double>,less<double>> small;
int size;
};
因为要将较大的数放在小顶堆把较小的数放在大顶堆中，所以每次add时都要视把数加到哪个堆，和另一个堆的堆顶进行比较。同时，还应该判断堆是否为空。
15、牛牛摘苹果（ZJ）
题目
牛牛有一个苹果园。又到了一年一度的收获季，牛牛现在要去采摘苹果买给市场的摊贩们。
牛牛的果园里面有n棵苹果树，第i棵苹果树上有ai个果子。
牛牛为了保证果子的新鲜程度，每天都会去苹果树上采摘果子。
牛牛特意安排一个计划表：
计划m天去采摘果子。
对于第i天，它会去所有果树上轮流采摘bi个果子。
如果对于第i天，某棵果树上没有bi个果子，那么它只会把当前果树上的果子采摘完。
牛牛想知道它每天能供应多少个苹果给市场的摊贩们。
输入:[10,20,10],[5,7,2]
输出:[15,17,2]
分析
这里用暴力法解并不难，但是如果出题人对时间复杂度提了要求，这题就难弄了。
先上代码，
vector<int> pick(vector<int> &a,vector<int> &b){
vector<int> ret(b.size(),0);
sort(a.begin(),a.end());
//当前要摘的总苹果数
int sum=0;
//pos前的苹果树都已经被摘空
int pos=0;
for(int i=0;i<b.size();++i){
sum+=b[i];
while(pos<a.size()&&a[pos]<sum){
//当前pos树上的苹果已经不够摘了，所以直接加上剩余的苹果数
ret[i]+=a[pos]-(sum-b[i]);
++pos;
}
ret[i]+=(b.size()-pos)*b[i];
}
return ret;
}
这里的思路是假设所有的苹果都是在第一天摘的，我们维护一个sum指针来表示当前要摘的苹果总数，如例题中，第一天是5，第二天是12，第三天是14。
一开始先将苹果数组排序，同时把sum加上第i天要摘的苹果数，
然后用sum与苹果的数量进行比较，如果sum>=当前苹果树上苹果的数量，表示这个苹果这次将被摘空，这里直接加上苹果树上剩余的苹果数。同时这里为防止重复访问，维护一个pos指针，表示还有剩余苹果的树的位置（这意思一开始要排序的原因）。
否则，就计算当前树以及以后树的总数，直接加上总数乘以这次要摘的苹果数量，因为后面的苹果数肯定也是够的（另一个一开始要排序的原因）。
复杂度
时间复杂度：O(N)
空间复杂度：O(1)
16、存在重复元素III
题目
分析
这题主要考察对红黑树set的使用，
题目的意思是指，在数组 nums[i] 中，在任意有效区间 [i, i + k] 里是否存在两个数的绝对值小于等于 t，即
|nums[i] - nums[j] | <= t
等价于 nums[i] - nums[j] <= t 并且 nums[i]−nums[j]>=−t。
也即，nums[i]<=t+nums[j] 并且 nums[i] >= nums[j] - t。
于是我们可以把nums中的值存进set中，然后在set中找是否存在nums[i]使得nums[i]<=t+nums[j] 并且 nums[i] >= nums[j] – t。
这里set的查找操作需要用到如下函数
std::set::upper_bound 是 >
std::set::lower_bound 是 >=
代码如下：
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n=nums.size();
set<double> haved;
for (int i=0;i<n;++i){
auto cur=haved.lower_bound((double)nums[i]-(double)t);
if(cur!=haved.end()&& *cur<=(double)nums[i]+(double)t) return true;
haved.insert(nums[i]);
if(haved.size()>k){
haved.erase(nums[i-k]);
}
}
return false;
}
复杂度分析：
时间复杂度：O(N\log K)，遍历数组使用 O(N)，在遍历的同时向二叉搜索树中插入元素和移除元素的时间复杂度是O(logK)。
空间复杂度：O(1)。