【***数组***】

数组理论基础

• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的

C++中，二维数组的内存空间也是线性的连续的

二分查找

704. 二分查找 - 力扣（LeetCode）

对于比较简单的二分查找来说，重点就是while里的条件和l,r指针的移动

第一种写法【l,r】内搜索

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0;
        int r=nums.size()-1;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return -1;
    }
};

第二种写法【l,r)内搜索 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0;
        int r=nums.size();
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        return -1;
    }
};

移除元素

27. 移除元素 - 力扣（LeetCode）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0,fast=0;
        for(;fast<nums.size();fast++){
            if(nums[fast]!=val)
                nums[slow++]=nums[fast];
        }
        return slow;
    }
};

有序数组的平方

 977. 有序数组的平方 - 力扣（LeetCode）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        int n=nums.size()-1;
        vector<int> ans(nums.size(),0);
        
        while(l<=r){
            if(nums[l]*nums[l]>nums[r]*nums[r] ){
               ans[n--]=nums[l]*nums[l];
                l++;
            }
            else{
                ans[n--]=nums[r]*nums[r];
                r--;
            }
        } 
        return ans;
    }
};

长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = 100005;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int Length = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                Length = (j - i + 1); // 取子序列的长度
                result = min(result,Length);
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == 100005 ? 0 : result;
    }
};