（c++）数组笔试测总点总结

# 数组

一、理论基础

1.数组内存空间地址是连续的，数组下标从0开始，地址表示16进制

2.数组的元素不能删除，只覆盖：删除指定下标元素，后面内容前移；

二、二分查找

1.使用条件：有序数组且数组中无重复元素

2.边界条件：

```
//左闭右闭，二分查找中间值为middle-1，闭区间说明可以取到
class Solution{
public:
int search(vector& nums,int target){
int left=0;
int right=num.size()-1;//左闭右闭
while（left<=right）
{
int middle = (right-left)/2+left;
if (num[middle]>target)
{
right=middle-1;//target在左区间
}else if(num[middle] {
left= middle+1;//target在右区间
}else
{
return middle
}
}
}
return -1; //为找到目标值
}
```

```
//左闭右开，二分查找中间值为middle，右区间不能取到
class Solution{
public:
int search(vector& nums,int target){
int left=0;
int right=num.size();//左闭右开
while（left {
int middle = ((right-left)>>1)+left;//（right+left）//2
if (num[middle]>target)
{
right=middle;
}else if(num[middle] {
left= middle+1;
}else
{
return middle
}
}
}
return -1; //为找到目标值
}
```

三、移除元素

1.暴力解法：时间复杂度O(n^2);空间复杂度O（1）。

2.快慢指针法：时间复杂度O(n);空间复杂度O（1）

四、有序数组平方

1.暴力解法：直接平方，再快速排序

2.双指针法：指向数组的首尾，比较其平方大小。

五、长度最小的子数组

1.滑动窗口法：考虑窗口是什么？，窗口的起始位置与结束位置如何移动

六、螺旋矩阵||

1.坚持左闭右开原则，注意旋转顺序。

TRANSLATE with

Bing Webmaster Portal