数组是存放在连续内存空间上的相同类型数据的集合。
数组下标都是从0开始的。
数组内存空间的地址是连续的。

数组的元素是不能删除的，只能覆盖。换言之，由于数组在内存空间上的地址是连续的，所以我们在删除或者增添元素的时候，就需要移动其他元素。

二维数组的内存空间在C++上是连续的，但是在java等其他语言中就不一定了。

二分法查找元素

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);
            if(target < nums[middle]) {
                right = middle -1;
            }
            else if(target > nums[middle]) {
                left = middle + 1;
            }
            else{
                return middle;
            }
        }
        return -1;
    }
};

暴力解数组去除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0; i <= size-1; i++ ){
            if(nums[i] == val){
                for(int j = i; j <= size -2; j++){
                    nums[j]= nums[j + 1];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

有序数组的平方
暴力解法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            nums[i] *= nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

双指针解法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};