当前位置：首页 > news >正文

【算法】【数组与矩阵模块】求最长可整合子数组和子数组的长度

news 2025/8/23 20:53:06

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
可整合数组定义：如果数组排序后，相邻元素之间差值为1的话，则该数组为可整合数组
给定一个数组arr，求arr中最长的可整合子数组。
如：5532643
返回53264，长度为5

解决方案

原问题：
首先有个定律：相邻元素差值为1的话，该数组的最大值和最小值差值+1就应该是数组的长度
根据该定律遍历数组的所有子数组，每一轮检测数组最大值和最小值差值是否是当前数组长度，求出最长长度即可。

代码编写

java语言版本

原问题：

/*** 二轮测试：求代码可整合子数组的最长长度* 可整合数组定义：对数组排序后，数组中每相邻两个数之间的差值为1* @param arr* @return*/public static Record getLILCp1(int[] arr) {if (arr == null || arr.length == 0) {return null;}Record record = new Record();int min;int max;// 用来判重Set<Integer> set = new HashSet<>();// 遍历每一个子数组for (int i = 0; i < arr.length; i++) {// 每一轮需要清空最值min = arr[0];max = arr[0];set.clear();for (int j = i; j < arr.length; j++) {// 子数组为[i...j],先计算最值// 更新当前子数组的最大值或最小值max = Math.max(max, arr[j]);min  = Math.min(min, arr[j]);// 计算当前子数组是否是可整合数组if (set.contains(arr[j])) {// 从j开始存在重复的,直接下一轮break;}else if (max - min + 1 == j - i + 1) {// 值域 == 长度if (j - i + 1 > record.len) {record.setLen(j - i + 1);record.setArr(Arrays.copyOfRange(arr, i, j+1));}set.add(arr[j]);}}}return record;}/*** 存储最长子数组长度和对应子数组的实体类*/static class Record {private int len;private int[] arr;public int getLen() {return len;}public void setLen(int len) {this.len = len;}public int[] getArr() {return arr;}public void setArr(int[] arr) {this.arr = arr;}@Overridepublic String toString() {return "Record{" +"len=" + len +", arr=" + Arrays.toString(arr) +'}';}}public static void main(String[] args) {System.out.println(getLILCp1(new int[]{5,5,3,2,6,4,3}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题给我两个启发：
首先求符合要求的子数组类型的问题一定能够通过暴力解决
符合要求的子数组可以通过暴力算法遍历每一个子数组，这道题我一开始往最优解上想的时候，根本没有考虑过使用暴力遍历每一个子数组，虽然可能大多数题目都不会这么写，但是不代表所有的题最优解不会遍历所有子数组。
其次长度和最值差值之间的关系需要记牢
相差1可以用长度等于最值差值这个定律在我刚开始接触算法的时候可能没有想到过，但是数组计数算法也有相似的启发，有时候我们可以多想想数组的index和实际的值有时候是否存在微妙的关联是很重要的。