leetcode 数组总结篇

2025/4/5 17:31:43 来源：https://blog.csdn.net/luckyme_/article/details/147003524 浏览: 次关键词：leetcode 数组总结篇

基础理论

数组：下标时从 0 开始的，地址是连续的，不能删除，只能覆盖；
数组的实现：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]