数组
大家好，我是老马。
今天我们一起来学习一下数组这种数据结构。
主要知识
数组需要拆分下面几个部分：
-
理论介绍
-
源码分析
-
数据结构实现？
-
题目练习（按照算法思想分类）
-
梳理对应的 sdk 包
-
应用实战
因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。
为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。
简单介绍1，重点为4。其他不是本系列的重点。
T26 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 已按 非严格递增 排列
v1-双指针
思考
这一题其实严格来说，不应该算简单。
因为有 2 个限制：原地删除+相对顺序保持一致
基本就把可能性限制死了，也就是双指针。
当然，如果知道的话，实现并不算难。
思路
left=结果的位置索引 right=正常遍历
二者可以从1开始，因为第一个数不和任何数重复。
nums[i] == nums[i-1] 则重复
nums[i] != nums[i-1] 则不重复，可以 left++，将 nums[left] == nums[right]
实现
public int removeDuplicates(int[] nums) {
if(nums.length <= 1) {
return nums.length;
}
int left = 1;
int right = 1;
for(right = 1; right < nums.length; right++) {
// 不重复
if(nums[right] != nums[right-1]) {
nums[left] = nums[right];
left++;
}
}
return left;
}
效果
0ms 100%
反思
这一题，其实和 T27 非常类似。
双指针的模板大概可以总结一下
public int removeDuplicates(int[] nums) {
// 根据题目，设置合理的初始化条件
int left = 1;
int right = 1;
for(right = 1; right < nums.length; right++) {
// 处理条件
if(nums[right] != nums[right-1]) {
nums[left] = nums[right];
left++;
}
}
return left;
}
小结
这一题限制条件比较多，基本就是固定了只能用双指针来解决。
数组基本知识+技巧
| 分类 | 代表技巧 |
|---|---|
| 遍历类 | 遍历、双指针、滑窗 |
| 前缀/差分类 | 前缀和、差分、后缀数组 |
| 查找类 | 二分、哈希、离散化 |
| 空间/状态优化 | 状压、滚动数组、差分压缩 |
| 排序/归并类 | 排序、归并逆序对、树状数组、线段树 |
| 子数组/序列 | 动规、中心扩展、单调栈 |
| 矩阵类 | 二维差分、DFS/BFS、旋转模拟 |
| 特殊技巧 | 快速幂、滚动哈希、模拟题技巧 |
🎯 常见遍历技巧 + 力扣题目对照表
| 技巧 | 力扣题目 | 说明 |
|---|---|---|
| 基础遍历 | 27.移除元素 | 直接遍历+判断 |
| 快慢指针 | 26. 删除重复项 | 原地去重 |
| 左右夹逼 | 167.两数之和 II | 排序+夹逼 |
| 滑动窗口 | 209. 长度最小子数组 | 动态控制窗口 |
| 子数组枚举 | 560. 和为K的子数组 | 前缀和优化 |
| 子序列枚举 | 491. 递增子序列 | 回溯 |
| 倒序遍历 | 198. 打家劫舍 | 动态规划 |
| 规则模拟 | 54. 螺旋矩阵 | 控制方向循环遍历 |
