数组
大家好，我是老马。
今天我们一起来学习一下数组这种数据结构。
主要知识
数组需要拆分下面几个部分：
-
理论介绍
-
源码分析
-
数据结构实现？
-
题目练习（按照算法思想分类）
-
梳理对应的 sdk 包
-
应用实战
因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。
为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。
简单介绍1，重点为4。其他不是本系列的重点。
相关题目
本质：贪心+合并区间
【leetcode】力扣 数组 array-02-56. 合并区间
扫描线专题
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1： 输入：s = “ababcbacadefegdehijhklij” 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”、”defegde”、”hijhklij” 。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。 示例 2：
输入：s = “eccbbbbdec” 输出：[10]
提示：
1 <= s.length <= 500 s 仅由小写英文字母组成
v1-贪心
思路
因为相同的 char 必须在同一个字符子串中，所以对于任何一个 char，记录在这个字符串种最右边的位置即可。
-
扫描字符串，记录每个字符的最后出现位置
last[c] -
从左到右遍历，用 end 表示当前分区最远边界（遍历到的所有字符的最大 last）
-
当
i == end时，一个分区结束，记录长度
PS: 这里使用数组哈希替代 HashMap，原理一样。
实现
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// 每遇到一个新字符，就看看它的尾巴（最后出现位置）会不会把当前区间拉长，Math.max 就是为了保证这段区间把所有相关字符都包住。
end = Math.max(end, last[s.charAt(i) - 'a']);
// 意味着当前走到的下标 i 已经到达了这一段的最远边界，说明这一段已经“封口”，不会影响后面的分段。
if (i == end) {
// 当前 part 结束
res.add(end - start + 1);
// next
start = i + 1;
}
}
return res;
}
复杂度
时间复杂度：O(n)
空间复杂度：O(1)（固定 26 个字母）
v2-转换为 LC56 来解决
TBC…
结果
1ms 击败 100.00%
