数组

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;
  }