一、数组基础

数组是存放在连续内存空间上的相同类型数据的集合，也就是说数组内存空间的地址是连续的。
因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址，注意：数组的元素是不能删的，只能覆盖。

1、数组初始化分配内存
int record[26] = {0};
2、vector排序函数：sort(A.begin(),A.end());
3、vector res = {1, 2, 3, 4};
4、vector int res(10,0); // 创建一个大小为10的vector
vector<vector> res(10, vector(10, 0)) // 创建一个10*10的二维vector
5、查找vector中的元素

vector<int>::iterator aa = find(visited.begin(), visited.end(), 5);  // 如果vector是空的，出现段错误
if (aa == visited.end())  没找到
else *aa   找到了返回值

PS：vector的底层实现是array，但严格来讲vector是容器，不是数组。之后补充
6、二维数组

int array[2][3] = {{0, 1, 2},{3, 4, 5}};
vector<int> res(10,0); // 创建一个大小为10的vector
vector<vector<int>> res(10, vector<int>(10, 0));

二维int型数组内存地址，相邻数组元素差了4个字节

二、题

1. 704 二分查找

前提条件：有序数组、无重复元素
着重点：
1、while的退出条件非常重要，小于等于：while(left <= right)
2、取中间值索引时非常重要：int mid = (right - left)/2 + left;
奇数个索引刚好在中间，偶数个索引在中间偏左位置

2. 27 移除元素

题目描述：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

双指针，感觉很难想，需要重点2刷。
核心思想：每次fast都会给slow值，除非fast指向了val

代码如下（示例）：

int removeElement(vector<int>& nums, int val) {int slow = 0;int fast = 0;while(fast < nums.size()){  // 每次fast都会给slow值，除非fast指向了valif(nums[fast] != val){nums[slow] = nums[fast];slow++;}fast++;}return slow;
}// 2021年第一次做
int fast = 0;
int slow = 0;
int removeElement(vector<int>& nums, int val) {for(fast = 0;fast<nums.size();fast++){if(nums[fast] != val) //在快和慢没有分开时，当快指针不为val时，带着slow走{                     //在快和慢分开之后，，当快指针不为val，每次赋值结束，slow指针自加nums[slow] = nums[fast]; //只要不赋值，慢指针就永远不自加slow++;}//当快指针为val时，快指针自己走，第一次快与慢分开的时候就是第一次碰到val的时候}return slow;
}

3. 977 有序数组的平方

vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int> res(nums.size(),0);int left = 0;int right = nums.size() - 1;while(right >= left){if(nums[right] * nums[right] >= nums[left] * nums[left]){res[k] = nums[right] * nums[right];k--;right--;}else{res[k] = nums[left] * nums[left];k--;left++;}}return res;
}

4. 209 长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

这题做的时候思维僵化了，没有利用好≥这个条件，总觉得应该固定窗口的大小再滑动，没想到可以动态条件窗口的大小，用了三种解法都是暴力解，之后可以看看。
做这题时同时复习了哈希映射和earse函数：
1、earse输入的是数组的迭代器，例：vector.erase(vector.begin());
2、遍历哈希映射的方式
for (auto it = windowfalse.begin(); it != windowfalse.end(); it++)
cout << *it << endl;

// 必须使用单for来完成滑窗
int minSubArrayLen(int target, vector<int>& nums) {int res = 999999999;  //INT32_MAXint sum = 0;int k = 0;int left = 0;for (int right = 0; right < nums.size(); right++) {sum += nums[right];while (sum >= target) {k = right - left + 1;res = res > k ? k : res;  // 题目要求是最小的长度，这个k不一定最小，暂时保存一下sum -= nums[left];left++;  // 动态滑窗！！窗口的大小不是固定的}}return res == 999999999 ? 0 : res;
}int minSubQueueLen(int target, vector<int> nums) {// 滑窗size为k时for (int k = 1; k < nums.size() + 1; k++) {unordered_set<int> windowfalse;queue<int> window;for (int i = 0; i < nums.size(); i++) {window.push(nums[i]);if (i >= k) {// windowfalse.erase(nums[i - k]);  // 哈希映射会删除滑窗中的该元素。。window.pop();}int ans = 0;// cout << k << "滑窗";/*for (auto it = windowfalse.begin(); it != windowfalse.end(); it++){int a = *it;ans += a;}*/// queue是没有遍历操作的，这是很弱智的做法，时间复杂度太高for (int i = 0; i < window.size(); i++) {  ans += window.front();window.push(window.front());window.pop();}if (ans >= target)return k;}}return 0;
}int minSubvectorLen(int target, vector<int>& nums) {// 滑窗size为k时for (int k = 1; k < nums.size() + 1; k++) {vector<int> window;for (int i = 0; i < nums.size(); i++) {window.push_back(nums[i]);if (i >= k) {window.erase(window.begin());}int ans = 0;// 时间复杂度太高for (int i = 0; i < window.size(); i++) {ans += window[i];}if (ans >= target)return k;}}return 0;
}
// 超出时间限制。。双指针暴力解
int minSubArrayLen(int target, vector<int>& nums) {// 滑窗size为k时for (int k = 1; k < nums.size() + 1; k++) {int left = 0;for (int right = 0; right < nums.size(); right++) {if ((right - left) > (k - 1)) {left++;}int ansleft = left;int ansright = right;int ans = 0;while (ansleft <= ansright) {ans += nums[ansleft]; ansleft++;}if (ans >= target) {return k;}}}return 0;
}