笔试和面试中，除了字符串，另一类出现频率极高的问题便是与数组相关的问题。
解题思路：
先一般考虑“万能的”暴力穷举（递归、回溯），如求n个数的全排列或八皇后（N皇后问题）。
但因为穷举时间复杂度通常过高，所以需要考虑更好的方法。
如 分治法（通过分而治之，然后归并）；
以及 空间换时间（如活用哈希表）。
此外，选择合适的 数据结构 可以显著提升效率，如寻找最小的k个数中，用 堆 代替 数组，也可借鉴快排思想，中枢分区方法。
再有，如果题目允许排序，则可以考虑 排序。
寻找和为定值的两个数中，先排序，然后用 前后两个指针 往中间扫描。
而如果如果已经排好序了（如杨氏矩阵查找中），则想想有无必要二分，二分法。
但是，如果题目不允许排序呢？这个时候，
我们可以考虑 不改变数列顺序的 贪心算法（如 最小生成树Prim、Kruskal 及 最短路dijkstra）
或 动态规划（如 01背包问题，每一步都在决策）。
最后，注意细节处理，不要忽略边界条件，如字符串转换成整数。
int (*p)[10];// 首先(*p)，p是一个指针，int [10],是一个包含10个int的数组，该指针p指向，这个数组
// 是数组指针
int *p[10]; // 写成 int* p[10];比较合适，首先 [10]是一个包含 10个元素的数组，该元素类型为int*,即指向整形的指针
// 是指针数组
int a[10];// 整数数组
printf("%x\n",&a);// &a 是取一个数组的地址，是一个指针指向一个包含10个元素的数组，类型为 int (*p)[10];
printf("%x\n",a); // a 数组名，默认为数组首元素 a[0]的地址 和数组a的地址是同一个地址，该类型为指向一个整数的指针，即 int *p；
// 以上 &a 和 a 的值是一样的，是a[0]元素的存储地址，
// 但是含义不一样， &a指向了10个连续存储的整数, 而 a指向了一个 整数，即 a[0]
// 类似的
int (*p[])(int); // 函数指针数组。
// 首先(*p[]) 是一个指针数组，指向的类型为 int (int)是一个函数类型，输入一个int类型参数，输出一个int类型参数
int (*p())[]; // 返回数组指针的函数。
// 首先 (*p()) 是一个返回指针类型的函数，该指针类型指向 int [] 即整形数组，即,p是一个返回整形数组指针的函数
int *p()[] // 字面上可以解释为返回指针数组的函数，不过函数是不能返回数组的。
// () 是一个函数， 返回类型为 int* []，是一个指针数组
int *(*a())() // 这是一个函数，它没有参数，它的返回值是一个函数指针，这个指针指向的函数，也没有参数，且返回值是int型的指针。输入n个整数，输出其中最小的k个。
要求一个序列中最小的k个数，按照惯有的思维方式，
则是先对这个序列从小到大排序，
然后输出前面的最小的k个数。
至于选取什么的排序方法，我想你可能会第一时间想到快速排序
我们知道，快速排序平均所费时间为n*logn，
然后再遍历序列中前k个元素输出即可。
因此，总的时间复杂度：O（n * log n)+O(k)=O（n * log n）。
解法二
咱们再进一步想想，题目没有要求最小的k个数有序，也没要求最后n-k个数有序。
既然如此，就没有必要对所有元素进行排序。这时，咱们想到了用选择或交换排序，即：
1、遍历n个数，把最先遍历到的k个数存入到大小为k的数组中，假设它们即是最小的k个数；
2、对这k个数，利用选择或交换排序找到这k个元素中的最大值kmax（找最大值需要遍历这k个数，时间复杂度为O（k））；
3、继续遍历剩余n-k个数。
假设每一次遍历到的新的元素的值为x，把x与kmax比较：如果x < kmax ，用x替换kmax，
并回到第二步重新找出k个元素的数组中最大元素kmax‘；如果x >= kmax，则继续遍历不更新数组，直到，k个数是此时最小的 每次遍历，更新或不更新数组的所用的时间为O（k）或O（0）。故整趟下来，时间复杂度为nO（k）=O（nk）。
更好的办法是维护容量为k的最大堆，原理跟解法二的方法相似：
1、用容量为k的最大堆存储最先遍历到的k个数，同样假设它们即是最小的k个数；
2、堆中元素是有序的，令k1<k2<...<kmax（kmax设为最大堆中的最大元素）
3、遍历剩余n-k个数。
假设每一次遍历到的新的元素的值为x，把x与堆顶元素kmax比较：
如果x < kmax，用x替换kmax，然后更新堆（用时logk）；
否则不更新堆。
这样下来，总的时间复杂度:O（k+（n-k）*logk）=O（n*logk）。
此方法得益于堆中进行查找和更新的时间复杂度均为：O(logk)
（若使用解法二：在数组中找出最大元素，时间复杂度：O（k））。
int Cut(int a[], int low, int high){
int temp = a[low];// 区间第一个元素 可以随机选择 在替换到low的位置
while(low < high){
while((low < higt)&&(a[high] > temp)) --high;// 从右边向左寻找比 temp小的元素 a[higt]
a[low] = a[high];// 把比temp小的元素 放在 原来temp的位置(左边小的区域)
while((low < high)&&(a[low] < temp)) ++low;// 从左边寻找比 temp大的元素a[low] 放在右边 high的位置
a[high] = a[low];
}
a[low] = temp; // 临时变量 放在 中枢位置
return low; // 返回中枢位置
}
// 在数组a中选择k个最小的元素 块选 非递归调用
void QuickSelest(int a[], int low, int high, int k){
int index = Cut(a, 0, n-1);// 首先得到一个中枢
while(index != k-1){// 非递归调用
if(index > k - 1) index = Cut(a, low, index -1);// 左半部分小的元素个数大于k 在左半部分找 中枢
else index = Cut(a, index+1, high);// 左半部分小的元素个数小于k 右半部分还有，在右半部分找 中枢
}
// 打印
for(int i = 0; i<k; ++i) cout<<a[i];
cout << endl;
}
// 而快排为 是递归调用
void QuickSort(int a[], int low, int high){
int index;
if(low < high){
index = Cut(a, low, high);//选取中枢位置
QuickSort(a, low, index-1);//对左边快排
QuickSort(a, index+1, high);//对右边快排
}
}
// 二分查找 非递归版本
int BinarySearch(int a[], int low, int high, int key){
int mid;//中间元素
while(low < high){
int mid = low + ((high - low)>>1);//中间元素的 下标 在循环体内 不停的被改变
if( key < a[mid] ) high = mid - 1;// 查找的元素小于中值 高区间移至 mid-1
elae if(key > a[mid] ) low = mid + 1;// 查找元素大于中值， 将低区间移至 mid+1
else return mid;
}
return -1;//未找打 返回-1
}
// 二分查找 递归版本
int BinarySearch(int a[], int low, int higt, int key){
int mid = low + ((high - low)>>1);//中间元素的 下标
if(low < high){
if(key < a[mid]) return BinarySearch(a, low, mid-1, key);
else if(key > a[mid]) return BinarySearch(a, mid+1, high, key);
else return mid;
}
return -1;
}
输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
思路：暴力搜索 时间复杂度 n^2 其二，二分法（相当于用两个指针），从前后向中间搜索，看情况移动左右指针
代码如下
// 二分（若无序，先排序后二分），时间复杂度总为O(N log N)，空间复杂度为O（1）；
void findTwo2(int a[], int low, int high, int sum){
//sort(a, a+high+1); 如果数组非有序的，那就事先排好序O(N log N)
while(low < high){
if(a[low] + a[high] > sum) --high;//太大 right减少
else if(a[low] + a[high] < sum) ++low; //太小 low增加
else cout << a[low] << a[high] < endl;
}
cout << "Can't found" < endl;
}
总结
不论原序列是有序还是无序，解决这类题有以下三种办法：
1、二分（若无序，先排序后二分），时间复杂度总为O(N log N)，空间复杂度为O（1）；
2、扫描一遍X-S[i] 映射到一个数组或构造hash表，时间复杂度为O(N)，空间复杂度为O(N)；
3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：
有序O(N)，无序O(N log N + N)=O(N log N)，空间复杂度都为O(1)。
所以，要想达到时间O(N)，空间O(1)的目标，除非原数组是有序的（指针扫描法），
不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间 O(Nlog N)，空间O(1)），
或映射或hash（时间O(N)，空间O(N)）。时间或空间，必须牺牲一个，达到平衡。
综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时O(N)，空O(1)效应。
否则，如果要排序的话，时间复杂度最快当然是只能达到O(N log N)，空间O(1)则不在话下。
输入：int[]nums int target
输出：符合要求的所有情况
给定一个int类型的数组，sum2、sum3、sum4分别输出2、3、4个元素的和为target的所有结果，不能重复，并且结果从小到大排序。
【解法】：
三个题目均可以使用双指针的做法。首先对原始数组进行排序，排序的意义为：
（1）保证最后结果的有序性；
（2）从小到大的查找是否满足target，
若小于他，则start指针往前走 ++start，
若大于他，这end指针往回走 --end；
接着第一个指针从最小的元素开始，
第二个指针从最大的元素开始，通过对和与target进行比较，判断start和end的走向。
sum2可以不用循环，只需要两个指针。
同时sum2还可以有另一种解法，从左到右判断，采用一个集合保存判断过的结果，从集合中查找target-nums[i]是否存在；（n）
sum3采用一层循环，start从循环处的下一个元素开始（n`2）
sum4采用两层循环，第二层循环从第一层循环的i值开始，最内部start从第二层循环的下一个元素开始。(n`3)
题目描述
输入两个整数n和sum，从数列1，2，3.......n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。
01背包问题求解
解法一
注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相关的问题。
如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum - n, n - 1)；
如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。
0-1背包问题
0-1背包问题是最基础的背包问题，其具体描述为：
有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是Ci，得到的价值是Wi。
求解将哪些物品装入背包可使价值总和最大。
简单分析下：这是最基础的背包问题，特点是每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即F[i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
F[i, v] = max{F[i-1, v], F[i-1, v-Ci ] + Wi}
根据前面的分析，我们不难理解这个方程的意义：
“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），
那么就可以转化为一个只和前 i-1 件物品相关的问题。
即：
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为 F[i-1, v ]；
如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-Ci的背包中”，
此时能获得的最大价值就是F[i-1, v-Ci]再加上通过放入第i件物品获得的价值Wi。
list<int>list1;
void SumOfkNumber(int sum, int n)
{
// 递归出口
if (n <= 0 || sum <= 0)
return;
// 输出找到的结果
if (sum == n)
{
// 反转list
list1.reverse();
for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
cout << *iter << " + ";
cout << n << endl;
list1.reverse()//此处还需反转回来
}
list1.push_front(n); //放置进背包 当前占了n 前面剩余sum-n空间 典型的01背包问题
SumOfkNumber(sum - n, n - 1);//“放”n，前n-1个数“填满”sum-n
list1.pop_front();// 取出来 不放进去 前面还剩余sum的空间
SumOfkNumber(sum, n - 1); //不“放”n，n-1个数“填满”sum
}
事实上，当我们令currSum为当前最大子数组的和，maxSum为最后要返回的最大子数组的和，当我们往后扫描时，
对第j+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
如果currSum加上当前元素a[j]后不小于a[j]，则令currSum加上a[j]，
否则currSum重新赋值，置为下一个元素，即currSum = a[j]。
同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。
即：
currSum = max(a[j], currSum + a[j])
maxSum = max(maxSum, currSum)
举个例子，当输入数组是1, -2, 3, 10, -4, 7, 2, -5，那么，currSum和maxSum相应的变化为：
currSum： 0 1 -1 3 13 9 16 18 13
maxSum ： 0 1 1 3 13 13 16 18 18
参考代码如下： int MaxSubArr(int* a, int num){ int currSum = 0;//初始化 当前和 为0 int maxSum = a[0];//初始化 第一个元素为 最大和 for(int j = 0; j < n; ++j ){ currSum = (currSum + a[j] > a[j] ) ? (currSum + a[j]) : a[j]; maxSum = maxSum > currSum ? maxSum : currSum; } return maxSum; }
一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。
求总共有多少总跳法，并分析算法的时间复杂度。
如果只有1级台阶，那显然只有一种跳法。
如果有2级台阶，那就有两种跳的方法了：
一种是分两次跳，每次跳1级；
另外一种就是一次跳2级。
现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。
当n>2时，第一次跳的时候就有两种不同的选择：
一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；
另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。
因此n级台阶时的不同跳法的总数f(n)=f(n-1)+f(n-2)。
我们把上面的分析用一个公式总结如下：
/ 1 n = 1
f(n)= 2 n = 2
\ f(n-1) + f(n-2) n > 2
原来上述问题就是我们平常所熟知的Fibonacci数列问题。
可编写代码，如下：
longn long Fibonacci(unsigned int n){
int result[] = [0, 1, 2];
if (n <= 2)
return result[n];
else
return Fibonacci(n-1) + Fibonacci(n-2);
}
/ 1 n = 1
f(n)= 2 n = 2
4 n = 3 //111, 12, 21, 3
\ f(n-1) + f(n-2) + f(n-3) n > 3
可编写代码，如下：
longn long F(unsigned int n){
int result[] = [0, 1, 2, 4];
if (n <= 3)
return result[n];
else
return F(n-1) + F(n-2) + F(n-3);
}
解法一用的递归的方法有许多重复计算的工作，事实上，我们可以从后往前推，一步步利用之前计算的结果递推。+ 初始化时，dp[0]=dp[1]=1， 然后循环递推计算即可：dp[n] = dp[n-1] + dp[n-2]，当前解 等于前两次的和
参考代码如下：
// 1,1,2,3,5,8,13,21..
int ClimbStairs(int n){// n级台阶，可以一次调1个台阶和2个台阶两种选择，有多少种跳发
int dp[3] = {1, 1};// 保存当前值 上一次值 上上次值的数组
if(n <=1) return 1;
else {
for(int i = 2; i <= n; ++i){
d[2] = d[1] + d[0];
d[0] = d[1];
d[1] = d[2];// 更新数组的值
}
}
}
// 想兑换100元钱，有1,2,5,10四种钱，问总共有多少兑换方法。 递推公式 arr[j] += arr[j - dimes[i]];
const int N = 100;
int dimes[] = { 1, 2, 5, 10 };
int arr[N + 1] = { 1 };//存放每一个总钱数可以的兑换次数
int coinExchange(int n) //非递归实现
{
for (int i = 0; i < sizeof(dimes) / sizeof(int); ++i)//对于每一个面值
{
for (int j = dimes[i]; j <= n; ++j)// 遍历总钱数j ~ n
{
arr[j] = arr[j] + arr[j - dimes[i]];
//分为两种情况，
//总钱数j，如果没有换当前硬币i，那么是多少？arr[j]
//加上，如果换了当前硬币dimes[i]，总值减少为 j-dimes[i]，此时又是多少种兑换方法？arr[j-dimes[i]]
}
}
return arr[n];
}
输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
借鉴partition 分治 的实现一，我们可以考虑维护两个指针，
一个指针指向数组的第一个数字，我们称之为头指针，向右移动；
一个指针指向最后一个数字，称之为尾指针，向左移动。
这样，两个指针分别从数组的头部和尾部向数组的中间移动，
如果第一个指针指向的数字是偶数而
第二个指针指向的数字是奇数，我们就交换这两个数字。
因为按照题目要求，最终是为了让奇数排在数组的前面，偶数排在数组的后面，
所以头指针理应指向的就是奇数，尾指针理应指向的就是偶数，
故当头指针指向的是偶数且尾指针指向的是奇数时，我们就当立即交换它们所指向的数字。
代码实现：
// 判断是否为奇数
bool isOddNumber(int n){
return n & 1 == 1; // 奇数 的最后一个二进制位为1
}
// void OddEvenChange(int *a, int num){
if(a == NULL|| num == 0) return;// 空指针 以及长度为0 直接返回
int* low = a; // 头指针
int* high = a + num - 1; // 尾指针
while(low < high){
if(!isOddNumber(*high) --high;//如果 high指针指向的是偶数，正常，向前移 减小
else if(isOddNumber(*low) ++low;//如果 low指针指向的是奇数，正常，向后移 加大
else //否则都不正常，交换
//swap是STL库函数，声明为void swap(int& a, int& b);
swap(*pBegin, *pEnd);
}
}
本方法通过头尾两个指针往中间扫描，一次遍历完成所有奇数偶数的重新排列，时间复杂度为O(n)。
现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请通过两两交换任意两个球，
使得从左至右，依次是一些红球(类1)、一些白球(类2)、一些蓝球(类3)。
通过前面的分析得知，这个问题类似快排中partition过程，只是需要用到三个指针：
一个前指针begin(指向类1)，一个中指针current(指向类2)，一个后指针end(指向类3)，
current指针遍历整个数组序列，当:
current指针所指元素为 类1 时，与begin指针所指的元素交换，而后current++，begin++ ；
current指针所指元素为 类2 时，不做任何交换（即球不动）， 而后current++ ；
current指针所指元素为 类3 时，与end指针所指的元素交换， 而后，current指针不动(end指向的元素可能为类1 )，end-- 。
参考代码如下：
while( current<=end )
{
if( array[current] ==0 )
{
swap(array[current],array[begin]);
current++;
begin++;
}
else if( array[current] == 1 )
{
current++;
}
else //When array[current] =2
{
swap(array[current],array[end]);
end--;
}
}