数组

int array[5]  
std::array<int,5> 倡议应用std::array代替简略数组，平安可保护

1.数组下标都是从0开始
2.数组内存空间的地址是间断且数组元素的类型雷同
3.在删除或者削减元素的时候，就不免要挪动其余元素的地址
4.在C++中二维数组是间断散布的，int array[2][3],
然而二维vector不是间断的 vector<vector<int>> matrix(2, vector<int>(3));

35-搜寻插入地位-二分查找

左闭右开的写法，也就是[left, right)

//O(logn) + O(1)
int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0;
    int right = n; // 定义target在左闭右开的区间里，[left, right)  target
    while (left < right) { // 因为left == right的时候，在[left, right)是有效的空间
        int middle = ((right + left) >> 1);
        if (nums[middle] > target) {
            right = middle; // target 在左区间，在[left, middle)中
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在 [middle+1, right)中
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值的状况，间接返回下标
        }
    }
    // 别离解决如下四种状况
    // 目标值在数组所有元素之前 [0,0)
    // 目标值等于数组中某一个元素 return middle
    // 目标值插入数组中的地位 [left, right) ，return right 即可
    // 目标值在数组所有元素之后的状况 [left, right)，return right 即可
    return right;
}

27-移除元素-快慢指针

    int removeElement(vector<int>& nums, int val) {
        //[3, 1, 2, 4, 6, 8, 2, 9, 0] val = 2
        //[3, 1, 4, 6, 8, 9, 0]
        int slow_idx = 0;
        for(int i = 0; i < nums.size() ++i){
            if(nums[i] != val){
                nums[slow_idx++] = nums[i];
            }
        }
    }

209-长度最小的子数组-滑动窗口

• 滑动窗口算法能够用以解决数组/字符串的子元素问题，它能够将嵌套的循环问题，转换为单循环问题，升高工夫复杂度。

  int minSubArrayLen(int target, vector<int>& nums) {
      //[2,3,1,2,4,3] target = 7
      //init  i = 0; j = 0; sum = 2;
      //step1 i = 0; j = 1; ->sum = 5 < 7; j++;
      //step2 i = 0; j = 2; ->sum = 6 < 7; j++;
      //step3 i = 0; j = 3; ->sum = 8 > 7; i++; subLength = 4;
      //step4 i = 1; j = 3; ->sum = 6 < 7; j++;
      //step5 i = 1; j = 4; ->sum = 10 > 7; i++; subLength = 4;
      //step6 i = 2; j = 4; ->sum = 7 = 7; i++; subLength = 3;
      //step7 i = 3; j = 4; ->sum = 6 < 7; j++;
      //step8 i = 3; j = 5; ->sum = 9 > 7; j++(x) i++(o); subLength = 3;
      //step9 i = 4; j = 5; ->sum = 7 = 7; j++(x) i++(o); subLength = 2;
      //step10 i = 5; j = 5; ->sum = 3 < 7; j++(x) i++(x);   
      int i = 0;
      int result = INT_MAX;
      int subLength = 0;
      int sum = 0;
      for(int j = 0; j < nums.size(); ++j){
          sum += nums[j];
          while(sum >= target){
              subLength = j - i + 1;
              result = min(subLength, result);
              sum -= nums[i++];
              //i++;
          }
      }
      return result == INT_MAX? 0 : result;
  }