数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合
数组徐璈注意的是：
- 数组的下标都是从0开始的
- 数组内存空间是的地址是连续的
正因为舒适的内存空间是连续的，所以在删除和增添元素的时候，需要移动其他元素的地址。
在c++中，vector的底层实现是array，严格来说，vector是容器，不是数组。
数组的元素不能删除，只能被覆盖。
704 二分查找
题目链接：https://leetcode.cn/problems/binary-search/
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
之前做过，但是现在一看还是很懵，没有一个清晰的解题思路。先看以便随想录上的解题思路，自己实现，总结收获。
解题思路：
首先需要看题的条件：有序数组，数组中无重复元素。如果是包含重复元素的数组，使用二分法查找返回元素下标可能不是唯一的。
区间的定义两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
第一种解法 左闭右闭：
[left, right]区间注意：
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
自己按照思路写出的代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = **nums.size()**-1;
while(left <= right){
//int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2 这里不是很懂。
**int mid = (right + left)/2;**
if(nums[mid] > target) {
**right = mid;** //这里应该是right=mid-1,因为如果当前mid对应的值大于目标值，应该在[left,mid-1]区间继续找，因为是双闭的区间。
}else if(nums[mid] < target){
**left = mid;** //所以这里也就是left = mid+1
}else return mid;
}
return -1;
}
};
总结：
vector的size .size()
为什么要用left + ((right - left) / 2)：
在计算中间值时，常见的表达式是 int middle = (left + right) / 2;。然而，当 left 和 right 是非常大的整数时，它们的和 left + right 可能会超过整数的最大值，从而导致溢出错误。此时，结果将是不正确的，可能会引发程序错误或崩溃。
第二种解法：左闭右开[left, right)
左闭右开时，仅需注意while(left < right) 两个不能相等
if(nums[mid] > target) right = mid; 即可
27.移除元素
题目链接：https://leetcode.cn/problems/remove-element/description/
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
题目分析：
原地：不使用额外的数组空间，在原地修改输入数组并在O(1)额外空间的条件下完成。
元素顺序可以改变，不需要考虑数组中超出新长度后面的元素。
暴力解法
思路：依次遍历数组中的所有元素，若等于val，size--，否则继续遍历。这时如何改变nums数组的值？即遇到值=val如何让数组后边的值覆盖前边的值。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0;i < size;i++){
if(nums[i] == val){
**for(int j = i+1; j < size; j++){ //遇到数组中值=val,让后一个数组值覆盖当前值**
** nums[j-1] = nums[j]; **
}
**i--;// i--是当前值被后值覆盖，所以是新值，在下一轮循环还需要针对当前的i值做判断**
size--;
}
}
return size;
}
};
重点 双指针法：
我的印象是设置一个fast一个slow指针。一个用于遍历数组，一个用于指示删除元素后数组的下标。
看完代码随想录后：
遇到数组值=val，fast继续向后遍历，slow不变，之后依次覆盖前面数组数值。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
int slow = 0;
for(int fast = 0; fast < size; fast++){
//错误写法 这里我想错了，总想等于val的时候应该做什么操作。
// if(nums[fast] == val){
// fast++;
// nums[fast-1] = nums[fast];
// }
// else slow++;
//只需要nums[fast] != val,才去给nums[slow]赋值就可以了。
if(nums[fast] != val)
nums[slow++] = nums[fast];
}
return slow;
}
};
总结：
暴力解法注意双层遍历让nums数组后值覆盖前值。
双指针法注意只有nums[fast] != val,再去给nums[slow]赋值。
977.有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
给你一个按 非递减顺序 排序的整数数组 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]
题目分析
数组是非递减，输出的新数组要求也按照非递减排序。
我的思路
这里给每一个数组元素平方在返回比较简单，但是如何返回的数组元素也按照非递减的顺序排列，没有太好的思路。依旧是双指针法，双指针怎么用？
看完随想录后
其实挺简单，让两个指针分别指向头和尾，定义一个新数组，两指针依次向中间遍历，看平方值的大小来判断哪个先放入新数组。
我的错误解法
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result;
int i = 0, j = nums.size()-1;
while(i <= j){
//应该预先分配好result的值，再向数组加元素，这样减少频繁push_back
//这个问题很大，我想的是如果i的nums值<j的nums值，就先向数组加入i的值，再加入j的值，这样是不对的。
if(nums[i] * nums[i] < nums[j] * nums[j]){
result.push_back(nums[i] * nums[i]);
result.push_back(nums[j] * nums[j]);
}
if(nums[i] * nums[i] == nums[j] * nums[j]){
result.push_back(nums[i] * nums[i]);
result.push_back(nums[i] * nums[i]);
}
i++;
j--;
}
return result;
}
};
正确解法：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(),0);
int i = 0, j = nums.size()-1;
//定义一个新的全局k值，用于新数组的下标值
int k = j;
while(i <= j){
// j--和i++只需要在其中nums[i]和nums[j]加入了新数组才用
if(nums[i] * nums[i] < nums[j] * nums[j]){
result[k--] = nums[j] * nums[j];
j--;
}else{
result[k--] = nums[i] * nums[i];
i++;
}
}
return result;
}
};
总结
我觉得最大的问题就是我总想着双指针i和j一起+或者-，这样是不对的，当满足条件仅改变其中一个就可以。