数组理论基础1. 定义连续内存空间 相同类型数据2. 数组下标下标索引→下标数据下标从0开始 内存空间地址连续3.下标连续→删除或者增添元素 → 移动其他元素的地址4. vector 和 array 的区别vector 的底层实现是 arrayvector 是容器不是数组5. 数组元素是不能删只能覆盖6. 二维数组a[0][1]前者为第一索引行后者为第二索引列7. C二维数组在地址空间上是连续的Java“数组的数组”一个指向行数组的引用行数组包含三个指向每一行数组的引用变量二分查找n个元素有序nums升序无重复元素和一个目标值target目的搜索nums里的target区间不变量边界的处理按照区间的定义操作→循环不变量规则e.g.左闭右闭leftright是成立的所以应该是while(leftright)左闭右闭[left,right]while(leftright) if(nums[middle]target){ rightmiddle-1 }左闭右开[left, right)while(leftright) if(nums[middle]target){ rightmiddle }力扣704class Solution { public: // 左闭右闭 int search(vectorint nums, int target) { int left 0; int right nums.size() - 1; while (left right) { int middle (left right) / 2; //忘记int if (nums[middle] target) { right middle - 1; } else if (nums[middle] target) { left middle 1; } else return middle; } return -1;//忘记写了 } };class Solution { public: // 左闭右闭 int search(vectorint nums, int target) { int left 0;//左闭右开 int right nums.size(); while (left right) { int middle (left right) / 2; if (nums[middle] target) { right middle; } else if (nums[middle] target) { left middle 1; } else return middle; } return -1; } };双指针暴力做法第一个for循环遍历数组元素第二个for循环更新数组On^2class Solution { public: int removeElement(vectorint nums, int val) { int sumnums.size(); for(int i0;isum;i){ if(nums[i]val){ for(int ji;jsum-1;j){//小心数组越界 nums[j]nums[j1]; } sum--; i--;//必不可少 } } return sum; } };双指针指针以下标移动代指针快慢指针快指针寻找新数组的指针不含目标元素的数组慢指针指向更新新数组下标的位置我的理解是快指针指向原数组进行筛选慢指针指向新数组进行覆盖本质上在原数组上进行操作class Solution { public: int removeElement(vectorint nums, int val) { int slow0; for(int fast0;fastnums.size();fast){ if(nums[fast]!val){ nums[slow]nums[fast]; } } return slow; } };有序数组的平方给你一个按非递减顺序排序的整数数组 nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。暴力做法先遍历数组将每个元素平方然后排序。class Solution { public: vectorint sortedSquares(vectorint nums) { for(int i 0; i nums.size(); i) { nums[i] * nums[i]; } sort(nums.begin(), nums.end()); return nums; } };双指针思想由于原数组已排序平方后的最大值只会出现在数组两端。可以使用左右双指针从两端向中间遍历。class Solution { public: vectorint sortedSquares(vectorint nums) { int k nums.size() - 1; vectorint results(nums.size(), 0); for(int i 0, j k; i j;) { if(nums[i] * nums[i] nums[j] * nums[j]) { results[k--] nums[i] * nums[i]; i; } else { results[k--] nums[j] * nums[j]; j--; } } return results; } };注意这里数组边界要减去 1for(int i 0, j k; i j;)是正确的不会数组越界。