1.数组基本知识点
1.1概念
数组就是一个集合。数组会用一些名为索引的数字来标识每项数据在数组中的位置，且在大多数编程语言中，索引是从 0 算起的。我们可以根据数组中的索引，快速访问数组中的元素。
数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。
1.2 相关操作的时间复杂度和空间复杂度
访问元素时间复杂度都是O(1)，空间复杂度O(1)，因为对于固定大小的数组，访问时间不随数组大小而变化。通过下标可直接访问。
修改元素：时间复杂度O(1)，空间复杂度O(1)，与n无关，通过下标可直接修改
插入元素和删除元素：时间复杂度O(1)，空间复杂度O(1)，插入和删除元素都需要移动后面的元素，因此随n变化。
题1：寻找数组的中心索引
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
解答思路：
第一步：先用for循环求总和
第二步：当位置为i时，找到其左边所有元素的合。
第三步：然后用总和减去其左边所有元素的合再减去当前元素的值。就是右边元素的值。
第四步：判断其左边元素和和右边元素和是否相等。
第五步：如果相等，则返回i，如果不相等，循环判断下一个元素。
第六步：如果最后一个元素仍然不满足，返回-1
代码案例：
class Solution
{
public:
int pivotIndex(vector<int> &nums)
{
int size = nums.size();
if (size <= 0)
{
return 0;
}
int sum = 0;
for (int &i : nums)
{
sum = sum + i; //第一步：先用for循环求总和
}
int leftsum = 0;
for (int i = 0; i < size; i++)
{
if (leftsum == (sum -leftsum - nums[i]))//第二步和第三步和第四步
{
return i; //第五步
}
leftsum += nums[i];//第五步
}
return -1;//第六步
}
};题2：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
解题思路：
思路：
第一步：此处特定说明了必须使用时间复杂度为 O(log n) 的算法。所以采用二分查找法。首先二分算法适用于已经排序过的数组。
第二步：二分法需要每次找到中间值，因此需要定义left，right，middle三个变量。
第三步：left=0，right = nums.size() - 1; middle = left + (right - left) / 2;
第四步：通过while循环进行查找
第五步：如果目标值刚好等于中间值，即target = nums[middle],则return middle；
第六步：如果目标值大于中间值，则说明其应该在右区间，因此需要挪动左边界值（left）为middle+1。
如果目标值小于中间值，则说明其应该在左区间，因此需要挪动右边界值（right）为middle-1。
第七步：如果最后左边界和右边界相等，此时会退出whlie循环，此时说明区间只有一个值了，判断其是否等于此值，如果大于等于则return left+1；就是新插入的位置。
如果此时目标值小于此值，则返回left的位置，要插入当前这个值的位置。
代码案例：
class Solution
{
public:
int searchInsert(vector<int> &nums, int target)
{
if (nums.size() <= 0)
{
return -1;
}
int left = 0;
int right = nums.size() - 1;
int middle = left + (right - left) / 2;
while (left < right)
{
middle = left + (right - left) / 2;
if (target == nums[middle])
{
return middle;
}
else if (target < nums[middle])
{
right = middle - 1;
}
else if (target > nums[middle])
{
left = middle + 1;
}
}
if (target >= nums[left])
{
return left + 1;
}
else if (target < nums[left])
{
return left;
}
else
{
return -1;
}
}
};题3：合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题思路：
思路：
一般需要后一个比前一个小的题，首先先思考排序
第一步：排序，确保第一个start小于第二个start
第二步：如果intervals[i].end >= intervals[i+1].start，则将其组合，选择两个end值中最大的那个
如果intervals[i].end < intervals[i+1].start，则无法合并，然后循环查找下一个区间和上一个区间再次进行循环对比
代码案例：
class Solution
{
public:
vector<vector<int>> merge(vector<vector<int>> &intervals)
{
if (intervals.size() == 1)
{
return intervals;
}
sort(intervals.begin(), intervals.end()); // 第一步：排序，确保第一个start小于第二个start
vector<vector<int>> returnvector;
returnvector.push_back(intervals[0]);//第二步：先放入第一个值，以此为判断
int j = 0;
for (int i = 1; i < intervals.size(); i++)
{
if (returnvector[j][1] >= intervals[i][0])//第三步：如果第一个值的end大于第二个值的start，则合并
{
returnvector[j][1] = max(returnvector[j][1], intervals[i][1]);//选择第一个值的end和第二个值end中最大的那个
}
else //否则，说明没有公共区间，则放入第二个
{
returnvector.push_back(intervals[i]);//只有合并完成，才会往后判断，否则一直基于此子数组进行合并
j++;
}
}
return returnvector;
}
};题4：旋转矩阵
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
思路：
这种题主打一个蛋疼。记住规律即可。
如果是顺时针旋转二维矩阵，则先对角翻转，再水平翻转。
如果是逆时针旋转二维矩阵，则先水平翻转，再对角翻转。
代码案例：
class Solution
{
public:
void rotate(vector<vector<int>> &matrix)
{
int N = matrix.size();
// 第一步：先对角线反转
for (int i = 0; i < N; i++)
{
for (int j = i; j < N; j++)
{
swap(matrix[i][j], matrix[j][i]);
}
}
// 第二步：水平翻转
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N / 2; j++)
{
swap(matrix[i][j], matrix[i][N - 1 - j]);
}
}
}
};题5：零矩阵
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
示例 1：
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
思路：
第一步：遍历二维数组，找出为0的x下标和y下标，并保存起来。
第二步：然后两次循环将其他位置清0
代码案例：
class Solution
{
public:
void setZeroes(vector<vector<int>> &matrix)
{
int M = matrix.size();
int N = matrix[0].size();
vector<int> x;
vector<int> y;
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
if (matrix[i][j] == 0)
{
x.push_back(i);
y.push_back(j);
}
}
}
for (auto &i : x)
{
for (int j = 0; j < N; j++)
{
matrix[i][j] = 0;
}
}
for (auto &i : y)
{
for (int row = 0; row < M; row++)
{
matrix[row][i] = 0;
}
}
}
};