目录
1. 排序数组的合并
例1. 合并两个排序数组并返回（模板）
例2. 合并两个排序数组到其中一个长的数组上
例3. 合并k个排序数组
2. 数组中的第k大
例4. 未排序数组中的第K个最大元素 （模板）
例5. 未排序字符串数字数组中的第k大字符串
例6. 未排序数组中的中位数
例7. 两个排序数组的中位数
3. 子数组（subarray）相关
例8. 求最大子数组和（模板）
例9. 股票的最大利润(只买卖一次)
例10. 求最大子数组和_找2个不重叠子数组
例11. 股票的最大利润(可买卖多次)
例12. 求最小子数组和
例13. 最大子数组差
例14. 找和为 0 的子数组
例15. 找和最接近 0 的子数组
4. 双指针相关
例16. 找数组中和等于target的两个元素（2Sum）（模板）
例17. 找数组中和等于0的三个数（3Sum）
例18. 找数组中和最接近target的三个数（3Sum Closest）
例19. 找数组中和等于target的四个元素（4Sum）
例20. 数组划分 （Partition Array）
5. 颜色排序
例21. 三种颜色排序
例22. 多种颜色排序
6. 交错排序
例23. 交错正负数
1. 排序数组的合并 例1. 合并两个排序数组并返回（模板）描述：将按升序排序的整数数组A和B合并，新数组也需有序。来源：（lintcode 6 · 合并排序数组简单）样例 1： 输入：A = [1] B = [1] 输出：[1,1] 解释：返回合并后的数组。
样例 2： 输入：A = [1,2,3,4] B = [2,4,5,6] 输出：[1,2,2,3,4,4,5,6]
代码
有点类似 合并两个排序链表。只不过这里使用时vector相关的操作。
class Solution {
public:
vector mergeSortedArray(vector &A, vector &B) {
int i = 0;
int j = 0;
vector result; //第一次竟然错误的写成vector result(A.size()+B.size()) 这是定义一个vector放入指定数量的0先。
while (i < A.size() && j < B.size()) {
if (A[i] < B[j]) {
result.push_back(A[i++]); //先插入，再指向下一个元素
} else {
result.push_back(B[j++]);
}
}
while (i < A.size()) {
result.push_back(A[i++]);
}
while (j < B.size()) {
result.push_back(B[j++]);
}
return result;
}
};当然后面两个while循环，也可以使用 if判断 + insert插入。注意这里迭代器加法的使用。
if (i < A.size()) {
result.insert(result.end(), A.begin() + i, A.end());
}
if (j < B.size()) {
result.insert(result.end(), B.begin() + j, B.end());
}描述： 合并两个排序的整数数组A和B变成一个新的数组。你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。数组A和B分别含有m和n个数。（来源：lintcode 64 · 合并排序数组（简单版）= leetcode 88. 合并两个有序数组）样例 输入：A = [1,2,3] m = 3; B = [4,5] n = 2 输出：[1,2,3,4,5]
代码
因为要合并到一个长的数组上，所以可以从后往前合并。其他的同例1。在最后处理时，当长数组还有剩余时不用处理，因为本身已经有序且在目标位置上。短的数组则需要重新放入长的数组中。注意这里 定义的当前位置的起始位置： cur = m + n - 1;
class Solution {
public:
void mergeSortedArray(int A[], int m, int B[], int n) {
int i = m - 1;
int j = n - 1;
int cur = m + n - 1;
while (i >=0 && j >= 0) {
if (A[i] > B[j]) {
A[cur--] = A[i--];
} else {
A[cur--] = B[j--];
}
}
while (j >= 0) {
A[cur--] = B[j--];
}
}
};描述: 将 k 个有序数组合并为一个大的有序数组。（来源：lintcode 486 · 合并k个排序数组）样例 1: 输入: [ [1, 3, 5, 7], [2, 4, 6], [0, 8, 9, 10, 11] ] 输出: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]样例 2: 输入: [ [1,2,3], [1,2] ] 输出: [1,1,2,2,3]挑战: 在 O(N log k) 的时间复杂度内完成：N 是所有数组包含的整数总数量。k 是数组的个数。
代码
这和 合并k个链表 是类似的。要求O(N log K)，应该自然想到二分法，即此处的归并排序。
class Solution {
public:
vector mergekSortedArrays(vector &arrays) {
vector result;
if (arrays.size() == 0) {
return result;
}
int k = arrays.size();
return mergeSortedArraysCore(arrays, 0, k - 1);
}
vector mergeSortedArraysCore(vector & arrays, int start, int end) {
if (start == end) {
return arrays[start];
}
int mid = start + (end - start) / 2;
vector left = mergeSortedArraysCore(arrays, start, mid);
vector right = mergeSortedArraysCore(arrays, mid+1, end);
return mergeTwoArrays(left, right);
}
vector mergeTwoArrays(vector A, vector B) {
//同例1（合并两个数组） 一模一样
};描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。（来源：leetcode 215. 数组中的第K个最大元素 = lintcode 5 · 第k大元素 ≈ lintcode 606 · 第K大的元素 II）示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
代码
可以使用优先队列（priority_queue, 内部实现堆（堆内部实现平衡二叉树）），定义一个只含k个数的优先队列，以小顶堆（priority_queue que;）的形式存储，当该优先队列存满后，下一个值若比当前堆顶元素（nums[i] > que.top()）大，则去掉堆顶元素，插入当前元素，此时小顶堆仍然自动保持有序。则第k大元素即为当前小顶堆的top元素。
class Solution {
public:
int findKthLargest(vector& nums, int k) {
int n = nums.size();
if (n < k) {
return -1;
}
priority_queue que; //特别注意：小顶堆，谁大谁放二叉树底层。
for (int i = 0; i < n; i++) {
if (que.size() < k) {
que.push(nums[i]);
} else {
if (nums[i] > que.top()) { //特别注意：大的替换小的，最终剩下k个最大的，小顶堆中的top元素，就是第k个最大的元素
que.pop();
que.push(nums[i]);
}
}
}
return que.top();
}
};拓展：当然该题，还可以使用快排中的patition方法来做。详见本文例6-代码2 。
例5. 未排序字符串数字数组中的第k大字符串描述：给你一个字符串数组 nums 和一个整数 k 。nums 中的每个字符串都表示一个不含前导零的整数。返回 nums 中表示第 k 大整数的字符串。注意：重复的数字在统计时会视为不同元素考虑。例如，如果 nums 是 ["1","2","2"]，那么 "2" 是最大的整数，"2" 是第二大的整数，"1" 是第三大的整数。（来源：leetcode 1985. 找出数组中的第 K 大整数）示例 1： 输入：nums = ["3","6","7","10"], k = 4 输出："3" 解释：nums 中的数字按非递减顺序排列为 ["3","6","7","10"] 其中第 4 大整数是 "3"示例 2： 输入：nums = ["2","21","12","1"], k = 3 输出："2" 解释：nums 中的数字按非递减顺序排列为 ["1","2","12","21"] 其中第 3 大整数是 "2"
提示：
1 middle，说明中位数在左侧，就只在左侧搜索；若 i < middle，说明中位数在右侧，只在右侧搜索。这样一次可以排除“一半”，从而减小了时间复杂度。注意代码中是如何缩小搜索范围的（使用 while(true) + 改变搜索边界 + 加1或减1）。（下面的middle 表示索引值，所以等于 int middle = (n - 1) / 2; ）
class Solution {
public:
int median(vector &nums) {
int n = nums.size();
if (n == 0) {
return -1;
}
vector A(nums.begin(), nums.end()); //为了不改变输入数组
int middle = (n - 1) / 2; //表示索引值。当题目要求找第k大元素时，此处变成 size - k 即可，其他完全一样。
int left = 0;
int right = n - 1;
while (true) { //特别注意: 这里使用的是 一直循环！！
int i = partition(A, left, right);
if (i == middle) {
return A[i];
} else if (i > middle) {
right = i - 1; //特别注意:这里要-1，为了防止各个数相等的情况，比如 0 0 0 0 0 2 1的情况
} else {
left = i + 1; //特别注意:这里要+1，为了防止各个数相等的情况，比如 0 0 0 0 0 2 1的情况
}
}
}
// 快排的 partition 部分， 当成一个积木块理解记忆
int partition(vector &nums, int start, int end) {
int i = start;
int j = end;
int key = nums[i];
while (i < j) {
while (i < j && nums[j] >= key) {
--j;
}
if (i < j) {
nums[i] = nums[j];
}
while (i < j && nums[i] = A.size()) { //当A遍历完了仍然没有找到，则必然存在B中，且是此层的B的第 bStart + k个元素。
return B[bStart + k - 1];
}
if (bStart >= B.size()) {
return A[aStart + k - 1];
}
if (k == 1) { // 当锁定到两个元素时，第1小的元素，则必然是两者中的min值。
return min(A[aStart], B[bStart]);
}
int a = (aStart + k/2 - 1 < A.size()) ? //当前比较对象：第 start + k/2 个元素，作为索引需要-1
A[aStart + k/2 - 1] : INT_MAX;
int b = (bStart + k/2 - 1 < B.size()) ?
B[bStart + k/2 - 1] : INT_MAX;
if (a < b) {
return findKthSmaller(A, B, aStart + k/2, bStart, k - k/2); //A前start+k/2个元素小，所以舍弃，从 start+k/2开始向后搜索，同时搜索长度减少k/2, 下面的类似。
} else {
return findKthSmaller(A, B, aStart, bStart + k/2, k - k/2);
}
}
};描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。(来源： lintcode 41 · 最大子数组 = leetcode 53. 最大子数组和 = leetcode 剑指 Offer 42. 连续子数组的最大和)示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
重要知识背景：
- 前缀和：索引为i的数的前面的所有数的求和（包含num[i]），记作 prefixSum[i]
- 则求索引 i ~ j 的子数组的和公式： prefixSum [j] – prefixSum [i-1]
- 这个公式是求子数组和中最最常用和普遍的公式。
- 则求到索引为i的数的最大子数组和 f[i] = prefixSum[i] – min(prefixSum(0~i-1))；即 当前位置的最大前缀和 = 当前位置的前缀和 - 之前最小的前缀和；整个数组的最大子数组和为：取所有位置最大前缀和的最大者。
根据上述描述，图示如下：
代码1
采用动态规划的方法。状态定义：dp[i] 表示以索引位置 i 结束的最大子数组的和 （则dp[i]包含元素nums[i]；dp[n-1]不是最终结果）；则状态转移方程为： dp[i] = max(nums[i], dp[i-1] + nums[i]); 然后去dp[i] 中最大的即为整个数组的 最大子数组和。（时间复杂度O(N) , 空间复杂度O(N)）
class Solution {
public:
int maxSubArray(vector& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
vector dp(n); //dp[i]表示以索引位置i结束的最大子数组和的值
dp[0] = nums[0];
int maxSum = nums[0];
for (int i = 1; i < n; i++) { //注意这里是从1开始的
dp[i] = max(nums[i], dp[i-1] + nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
};代码2
使用几个常量来记录 计算到当前位置i时的前缀和 curSum、计算到当前位置i时的最大子数组和（不一定包含元素nums[i]） maxSum(maxSum是最终结果)、当前数组中的最小子数组和 minSum，则 到计算到当前 位置时的 maxSum = max (maxSum, curSum - minSum)；（时间复杂度O(N) , 空间复杂度O(1)）
class Solution {
public:
int maxSubArray(vector& nums) {
int n = nums.size();
if (n == 0) {
return INT_MIN;
}
int maxSum = INT_MIN;
int minSum = 0;
int curSum = 0;
for (int i = 0; i < n; i++) {
curSum += nums[i]; //计算当前位置的前缀和
maxSum = max(maxSum, curSum - minSum); // 当前位置的最大前缀和=当前位置的前缀和 - 之前最小的前缀和，然后取所有位置最大前缀和的最大者。
minSum = min(minSum, curSum); //确保 minSum 是历史上的最小前缀和
}
return maxSum;
}
};描述：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？(来源：lintcode 149 · 买卖股票的最佳时机 = leetcode 剑指 Offer 63. 股票的最大利润)示例 : 输入: [7,1,5,3,6,4] 输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
代码1：
本题基本等价于例8-求最大子数组和。只需要做一个转换，将原始数组变成后一个数减前一个数组成一个新的数组，在这个新的数组上求最大子数组和，即为最大利润。比如数组A= [7,1,5,3,6,4] 变成 数组B=[-6,4,-2,3,-1]，然后求B的最大子数组和。注意：当小于0时取0。
class Solution {
public:
int maxProfit(vector& prices) {
// write your code here
if (prices.size() == 0 || prices.size() == 1) {
return 0;
}
vector nums;
for (int i = 1; i < prices.size(); i++) {
nums.push_back(prices[i]-prices[i-1]);
}
int max = maxSubArray(nums);
return max > 0 ? max : 0;
}
int maxSubArray(vector & nums) {
//完全同例8-求最大子数组和
}
};代码2：
同例8，只不过这里要处理的是当前状态时的最大利润，需要保存之前的最小股票值minValue.
依然类似于动态规划，dp[i]表示当前 i 时刻卖出的最大利润，则 dp[i] = max(dp[i-1], prices[i] - minValue)。这里不用保存每个状态，所以直接使用一个变量即 maxProfit 来表示状态。
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
if (n == 0) {
return 0;
}
int maxProfit = 0;
int minValue = prices[0];
for (int i = 1; i < n; i++) {
maxProfit = max(maxProfit, prices[i] - minValue); // 记录当前利润，并更新最大利润
minValue = min(minValue, prices[i]); // 记录当前最小值
}
return maxProfit; // 不用再跟0比较，因为maxProfit初始值是0，更新时使用max函数，意味着肯定大于0.
}
};描述：给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。子数组最少包含一个数。（来源：42 · 最大子数组 II）样例：输入：nums = [1, 3, -1, 2, -1, 2] 输出：7解释：最大的子数组为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2].
代码：
例8的拓展，基本模块同上一例题。只不过要找2个子数组。为了不重叠，一个从前往后找，并保存到达i位置时的最大子数组和（记作 maxLeft[i]），一个从后往前找（记作 maxRight[i]）；这样，maxLeft[i] 和 maxRight[i+1]就不重合了！ 然后，从所有的 maxLeft[i] + maxRight[i+1] 中取最大的即为最终要求结果。
- 本题 maxLeft[i] 含义：遍历到i位置的，历史最大子数组和；使用 curSum - minSum。
- maxSum = max(maxSum, curSum - minSum); maxLeft[i] = maxSum;
- 例13 maxLeft[i] 含义：遍历到i位置的，包含i位置的最大子数组和；看上一个值大于0就加上。
- （不同于例13: maxLeft[i] = max(nums[i], maxLeft[i-1] + nums[i]);）
class Solution {
public:
int maxTwoSubArrays(vector &nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
vector maxLeft(n);
int maxSum = INT_MIN;
int minSum = 0;
int curSum = 0;
for (int i = 0; i < n; i++) { // 从左往右计算
curSum += nums[i];
maxSum = max(maxSum, curSum - minSum);
minSum = min(minSum, curSum);
maxLeft[i] = maxSum; //注意：for循环最后保存当前的最大子数组和
}
vector maxRight(n);
maxSum = INT_MIN;
minSum = 0;
curSum = 0;
for (int i = n - 1; i >= 0; i--) { // 从右往左计算
curSum += nums[i];
maxSum = max(maxSum, curSum - minSum);
minSum = min(minSum, curSum);
maxRight[i] = maxSum;
}
int result = INT_MIN;
for (int i = 0; i < n - 1; i++) { // 在 左侧 + 右侧 中取最大值
result = max(result, maxLeft[i] + maxRight[i+1]);
}
return result;
}
};描述：给定一个数组 prices 表示一支股票每天的价格.交易次数不限, 不过你不能同时参与多个交易 (也就是说, 如果你已经持有这支股票, 在再次购买之前, 你必须先卖掉它).设计一个算法求出最大的利润. （来源：150 · 买卖股票的最佳时机 II = leetcode 122. 买卖股票的最佳时机 II）
样例：输入: [2, 1, 2, 0, 1] 输出: 2解释: 1. 在第 2 天以 1 的价格买入, 然后在第 3 天以 2 的价格卖出, 利润 1 2. 在第 4 天以 0 的价格买入, 然后在第 5 天以 1 的价格卖出, 利润 1 总利润 2.
代码
类似例9，同样可以用DP的方式解决。状态定义：dp[i] 表示索引为i那天交易可能获得的最大利润。状态转移方程：索引为i天时交易产生的最大利润等于 i-1 天产生的最大利润 加上 i-1天买入，i天卖出产生的利润。即 dp[i] = max (dp[i-1] , dp[i-1] + prices[i]-prices[i-1])。 这里可以使用一个变量 maxProfits 滚动相加, 即 maxProfits = max(maxProfits, maxProfits + prices[i]-prices[i-1]);
需要注意的是：maxProfits 初值不能是 INT_MIN, 因为在状态转移方程中它同时参与了max函数中两个比较对象的计算。
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
if (n == 0) {
return 0;
}
int maxProfits = 0; //注意不能是INT_MIN! // dp[i] 表示索引为i那天交易可能获得的最大利润
for (int i = 1; i < n; i++) { // dp[i] = max (dp[i-1] , dp[i-1] + prices[i]-prices[i-1])
maxProfits = max(maxProfits, maxProfits + prices[i]-prices[i-1]);
}
return maxProfits;
}
};描述：给定一个整数数组，找到一个具有最小和的连续子数组。返回其最小和。子数组最少包含一个数字。（来源：lintcode 44 · 最小子数组）样例 输入：数组 = [1,-1,-2,1] 输出：-3 解释：子数组[-1,-2]的和是最小值-3。
代码
这里给出2种方法，都基本等同于求最大连续子数组。方法1：数组取反，求最大连续子数组和，返回相反数。方法2：DP的方法，累计数组和，每次计算minSum = min(minSum, curSum - maxSum) 每次更新maxSum。
class Solution {
public:
int minSubArray(vector &nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int minSum = INT_MAX;
int curSum = 0;
int maxSum = 0;
for (int i = 0; i < n; i++) {
curSum += nums[i];
minSum = min(minSum, curSum - maxSum);
maxSum = max(maxSum, curSum);
}
return minSum;
}
};描述：给定一个整数数组，找出两个不重叠的子数组A和B，使两个子数组和的差的绝对值 |SUM(A) - SUM(B)| 最大。返回这个最大的差值。子数组最少包含一个数。（来源：lintcode 45 · 最大子数组差）
样例 1： 输入：数组 = [1, 2, -3, 1] 输出：6 解释：子数组是 [1,2] 和[-3].所以答案是 6.
样例 2： 输入：数组 = [0,-1] 输出：1 解释：子数组是 [0] 和 [-1].所以答案是 1. 挑战：时间复杂度为O(n)，空间复杂度为O(n)
代码
等同于 求最大子数组 + 最小子数组 + 不重叠子数组的要求。思路：维护四个数组，当前位置 i 左边的最大子数组和，最小子数组和。当前位置右边的最大子数组和，最小子数组和。然后枚举分割线，扫描一下取最大即可。状态定义比如：leftMax[i] 表示以索引位置i结束的最大子数组和；转移方程：leftMax[i] = max(nums[i], leftMax[i-1] + nums[i]); 其他3个数组类似。
class Solution {
public:
int maxDiffSubArrays(vector &nums) {
int n = nums.size();
if (n == 0 || n == 1) {
return 0;
}
vector leftMax(n); // leftMax[i]表示以索引位置i结束的最大子数组和的值
vector leftMin(n);
vector rightMax(n);
vector rightMin(n);
leftMax[0] = nums[0];
leftMin[0] = nums[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(nums[i], leftMax[i-1] + nums[i]);
leftMin[i] = min(nums[i], leftMin[i-1] + nums[i]);
}
rightMax[n-1] = nums[n-1]; // 特别注意：这里初始化的是最后一个元素！
rightMin[n-1] = nums[n-1];
for (int i = n - 2; i >= 0; i--) { //注意：是i--,别误写成++
rightMax[i] = max(nums[i], rightMax[i+1] + nums[i]);
rightMin[i] = min(nums[i], rightMin[i+1] + nums[i]);
}
int maxDiff = 0;
for (int i = 0; i < n - 1; i++) {
maxDiff = max(maxDiff, leftMax[i] - rightMin[i+1]);
maxDiff = max(maxDiff, rightMax[i+1] - leftMin[i]);
}
return maxDiff;
}
};描述：给定一个整数数组，找到和为 0的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置;至少有一个子数组的和为 0. (来源：lintcode 138.子数组之和)
样例 1: 输入: [-3, 1, 2, -3, 4] 输出: [0,2] 或 [1,3] 样例解释： 返回任意一段和为0的区间即可。样例 2: 输入: [-3, 1, -4, 2, -3, 4] 输出: [1,5]
代码
考虑到两个子数组的和为0，意味着不同的前缀和（累加到索引位置i的和，记为sum[i]）中有相等的，即 sum[i到j] = 0， 即 sum[i-1] = sum[j]。 在候选项中找相等，所以应自然相等使用hash数据结构。判断的是sum是否相等，所以将sum作为哈希的key，因为最终结果要的是索引值，所以索引值作为哈希的value。当判断有相等前缀和出现时，则返回上一个前缀和的索引 i 的后一个位置 （i+1）（也就是子数组和的第一个位置），以及当前索引值。
class Solution {
public:
vector subarraySum(vector &nums) {
vector result;
int n = nums.size();
if (n == 0) {
return result;
}
unordered_map hashMap;
int curSum = 0; //记录累加到当前索引i时的前缀和
hashMap.insert({0, -1}); //key表示 sum， value 表示索引位置(到索引为i(value)的位置的前缀和为sum(key))
for (int i = 0; i < n; i++) {
curSum += nums[i];
if (hashMap.find(curSum) != hashMap.end()) {
result.push_back(hashMap.at(curSum) + 1); //找到历史上的前缀和比如 前a个数，等于当前(索引为i)的前缀和，则子数组和为0的区间自然是 [a+1, i] // 或 hashMap[curSum] + 1
result.push_back(i);
return result;
}
hashMap.insert({curSum, i}); //注意 插入hashMap的方式！// 或 hashMap[curSum] = i;
}
return result;
}
};描述：给定一个整数数组，找到一个和最接近于零的子数组。返回满足要求的子数组的起始位置和结束位置。（来源：139 · 最接近零的子数组和）样例： 输入: [-3,1,1,-3,5] 输出: [0,2] 解释: [0,2], [1,3], [1,1], [2,2], [0,4] （注意：返回的是索引的 start 和 end 位置） 挑战：O(nlogn)的时间复杂度
代码
求最接近于0的子数组，意味着找两个前缀和，这两个前缀和的差（diff）最小。题目要求时 O(nlogn) ，应该自然想到要排序！ 所以这里，我们先把各个索引位置对应的前缀和求出来，组成一个个节点元素（Node(value, pos)）,然后对这些前缀和进行排序，则 前缀和相互接近 的自然排到了一起，然后就只需要看相邻两个元素，找出差最小的两个元素，则它们对应的索引即为所求。
特别注意：因为要排序，可以使用 pair(key, value)这样的结构，也可以为了使代码可读性更好，使用自定义的数据结构（文中自定义Node数据结构），然后需要重载 operator
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
