leetcode 数组总结篇

基础理论

1. 数组：下标时从 0 开始的，地址是连续的，不能删除，只能覆盖；
2. 数组的实现：vector动态数组

常用操作

头文件

#include <iostream>
#include <vector>
#include <cstdint>  // INT32_MAX
#include <algorithm> // min 函数
using namespace std;

创建 & 打印输出

// 一维数组
vector<int> nums = {1,2,3,4,5,6,7};// 一维数组，scanf输入元素
cin >> n;
vector<int> nums(n);
for(int i = 0; i < n; i++){scanf("%d",&nums[i]); // 一行输入一个元素
}// 二维数组，n*m的数组，默认值为0
vector<vector<int>> vec(n,vector<int>(m));// 二维数组，n*m的数组，默认值为1
vector<vector<int>> vec(n,vector<int>(m，1));// 二维数组，cin 输入元素
cin >> n >> m;
vector<vector<int>> vec(n,vector<int>(m));for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> vec[i][j];sum += vec[i][j];}
}// 二维数组的输出
void printVector(vector<vector<int>>& nums){cout << "[";for(int i = 0; i < nums.size(); i++){if(i != 0) cout << " ";// 子数组之间加空格分隔cout << "[";for(int j = 0; j < nums[i].size(); j++){cout << nums[i][j];if(j != nums[i].size() - 1) cout << ", ";//每行的最后一个元素不加逗号}cout << "]";if(i != nums.size() - 1) cout << ",";// 最后一个子数组不加逗号}cout << "]" << endl;
}

输入 & 打印输出

while(scanf("%d%d", &a, &b) == 2) // 一行输入两个元素
printf("%d\n",sum); // 一行输出一个元素

数组经典题目

1. 二分法

• 左闭右闭[left, right]：
  • while(left <= right)
    - if(nums[mid] > target) right = mid -1;
  • if(nums[mid] < target) left = mid + 1;
    - if(nums[mid] == target) return mid;
• 左闭右开[left, right)：
  • while(left < right)
    - if(nums[mid] > target) right = mid;
    - if(nums[mid] < target) left = mid + 1;
    - if(nums[mid] == target) return mid;
• 时间复杂度：O(logn)

2. 双指针：

移除元素和有序数组的平方

• 1. 移除元素：
  • 快指针：寻找新元素，不断的移向下一个元素，判断是否与target相等
  • 慢指针：指向新数组（不包含 target的数组）下标的位置
• 2. 有序数组的平方:
  • 指针 i ：数组起始位置；指针 j：数组终止位置
  • 新数组result 存储结果，k：数组终止位置
  • nums[i] * nums[i] >= nums[j] * nums[j] result[k--] = nums[i] * nums [i]
  • nums[i] * nums[i] < nums[j] * nums[j] result[k--] = nums[j] * nums[j]

3. 滑动窗口:

根据当前子序列的大小情况，不断调整子序列的起始位置和终止位置。使用一个for循环完成两个for循环的搜索。

• 窗口内：要维护的子序列
• 窗口的终止位置j ：for循环更新变量 j（外层）；
• 窗口的起始位置 i：窗口内元素的值不满足条件了，就要向前移动，while更新 i（内层）

4. 螺旋矩阵:

和二分法类似，首先要确定循环不变量，左闭右开

5. 前缀和：

找出指定区间[a, b]元素的总和 sum；

• 累加：p[i] 表示 下标 0 到 i 的 vec[i] 累加之和
• if (a == 0) sum = p[b]
• if(a != 0) sum = p[b] - p[a - 1]