数组理论

数组是存放在连续的内存空间上的相同类型数据的集合

在C++中，二维数组是连续分布的

java没有指针，不对程序员暴露其元素的地址，寻址操作完全交给虚拟机，所以看不到每个元素的地址情况。

704二分查找

链接: 二分查找

ac代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left,right,mid;
        left = 0;
        right = nums.size()-1;
        while(right>=left){ //判断条件是大于等于，否则只有一个元素的数组会会直接return -1；
        mid=(left+right)/2;
        if(nums[mid]>target){
            right =mid -1;
        }
        if(nums[mid]<target){
            left = mid+1;
        }
        if(nums[mid]==target)
        return mid;

        }
        return -1;
    }
};

二分法的关键在于：
1.while中是大于还是大于等于
2.right和left的更新
左闭右闭：while中大于等于，right=mid-1，left=mid+1.
左闭右开：while中大于，初始right=nums.size，right=mid，left=mid+1

移除元素

ac代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int tmp=nums.size();
        for(int i=0;i<tmp;i++){//注意循环条件是tmp不是nums.size()
            if(nums[i]==val){
                for(int j=i+1;j<tmp;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                tmp--;
            }
            
        }
        return tmp;
    }
};

vector的底层实现是array，严格来讲不是数组，是容器。

双指针思路：

// 时间复杂度：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 (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

思路为保留非val值而不是删除val值。