数组
1 数组理论基础
-
数组是存放在连续内存空间的相同类型数据的集合
-
数组下标都是从0开始的。
-
数组内存空间的地址是连续的
-
-
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
-
在C++中二维数组在地址空间上是连续的。
2 二分查找
题目：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
思路：
有序+无重复元素，那么我们可以使用二分法
注意：区间的选择会影响整个代码思路，比如选用[left,right]，也即左闭右开。
代码：
class Solution{
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = (right + left) / 2;
if(nums[mid] < target) left = mid + 1;
else if(nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
};
3 移除元素
题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
不需要考虑数组中超出新长度后面的元素。
思路：
- 暴力解法：两个for循环，第一个循环进行查询，若查询到指定值，则第二个for循环进行删除。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 双指针法：通过一个快指针，一个慢指针。两个指针同时从0开始，当快指针查询到val时+1，慢指针不变；否则快慢指针同时+1。结束条件为快指针到数组尾端。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){
if(nums[fastIndex]!=val) nums[slowIndex++] = nums[fastIndex];
}
return slowIndex;
}
};
4 有序数组的平方
题目：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
思路：
双指针法，leftIndex和rightIndex
- 时间复杂度：O(n)
- 空间复杂度：O(n)
代码：
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int leftIndex = 0;
int rightIndex = nums.size() - 1;
vector<int> result(nums.size(),0);
for(int i = nums.size() - 1; i >= 0; i--){
if(abs(nums[leftIndex]) > abs(nums[rightIndex])){
result[i] = nums[leftIndex] * nums[leftIndex];
leftIndex++;
}
else{
result[i] = nums[rightIndex] * nums[rightIndex];
rightIndex--;
}
}
return result;
}
}
5 长度最小的子数组
题目：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路：
-
暴力解法：两个for循环，外层i为区间起点，内层j为区间终点
- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
-
滑动窗口法：类似双指针法，一个while循环，同样有区间起点leftIndex和区间终点rightIndex。区间和小于target，rightIndex++，否则leftIndex++，并且记录rightIndex-leftIndex的最小值result，终止条件为rightIndex到达终点
代码：
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
6 螺旋矩阵Ⅱ
题目：
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路：
主要就是模拟螺旋的过程以及一些特殊情况，从外圈到内圈，最好在纸上模拟
代码：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n,vector<int>(n,0));
int startx = 0,starty = 0;
int mid = n / 2;
int loop = n / 2;
int offset = 1;
int num = 1;
int i,j;
while(loop--){
i = startx;
j = starty;
for(j = starty;j < n - offset; j++){
result[startx][j] = num++;
}
for(i = startx;i < n - offset; i++){
result[i][j] = num++;
}
for(;j >startx; j--){
result[i][j] = num++;
}
for(;i > starty; i--){
result[i][j] = num++;
}
startx++;
starty++;
offset += 1;
}
if(n % 2) result[mid][mid] = n * n;
return result;
}
};
7 总结
-
二分法
-
双指针法
-
模拟