ArrayMap 源码解析

2024-05-28 12:58
文章标签 源码 解析 arraymap

本文主要是介绍ArrayMap 源码解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、简述
  • 我们都知道 HashMap，它属于 java.util 包下，但是很多人可能对 ArrayMap 并不是很熟悉，通俗来说 ArrayMap 属于 android.util 包下，是用于 Android 平台某些情况替换 HashMap 的数据结构。
  • 使用限定：minSdkVersion 必须大于等于 19（Android 4.4）。
2、归纳
  • 实现了 Map 接口。
  • 底层采用两个一维数组，第一个数组是整型数组，且有序，存储 key 对应的 hash 值，第二个数组存储 key 和 value，其中 key 在 index*2 位置，value 在 index*2+1 位置。
  • 每次插入时，根据 key 的哈希值，利用二分查找，去寻找 key 在整型数组中的下标位置，如果出现了 hash 冲突，则从需要从目标点向两头遍历，找到正确的 index。
  • 扩容机制，如果容量小于4，则扩容到4，如果容量大于等于4小于8，则扩容到8，如果容量大于等于8，则扩容到当前容量加当前容量的一半。
  • 缩容机制，如果存储 hash 值的数组长度大于等于8，且集合长度少于当前空间的1/3，则进行收缩操作，避免浪费空间。
  • ArrayMap 的操作单线安全，多线程不安全。
  • 1000 以内元素性能 ArrayMap 相对 HashMap 更高。
3、分析
3.1、成员变量
public final class ArrayMap<K, V> implements Map<K, V> {// 是否是 DEBUG 模式private static final boolean DEBUG = false;// 设置 TAGprivate static final String TAG = "ArrayMap";private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;// 扩容默认的 size， 4是相对效率较高的大小private static final int BASE_SIZE = 4;// 数组缓存中的最大条目数@UnsupportedAppUsage(maxTargetSdk = 28)private static final int CACHE_SIZE = 10;// 指示容器不可变的特殊哈希数组值@UnsupportedAppUsage(maxTargetSdk = 28)static final int[] EMPTY_IMMUTABLE_INTS = new int[0];@UnsupportedAppUsage(maxTargetSdk = 28)public static final android.util.ArrayMap EMPTY = new android.util.ArrayMap<>(-1);@UnsupportedAppUsage(maxTargetSdk = 28)static Object[] mBaseCache;@UnsupportedAppUsage(maxTargetSdk = 28)static int mBaseCacheSize;@UnsupportedAppUsage(maxTargetSdk = 28)static Object[] mTwiceBaseCache;@UnsupportedAppUsage(maxTargetSdk = 28)static int mTwiceBaseCacheSize;private static final Object sBaseCacheLock = new Object();private static final Object sTwiceBaseCacheLock = new Object();// 是否利用 System.identityHashCode(key) 获取唯一 hashCodeprivate final boolean mIdentityHashCode;// 保存每个元素的 hash，长度为容量大小// mHashes 是有序的，按照元素的 hash 值由小到大排序，hash 值相同的元素，先插入的排在前面// 由于 mHashes 是有序的，所以使用二分法查找元素的位置，时间复杂度为 O(logn)@UnsupportedAppUsage(maxTargetSdk = 28)int[] mHashes;// 保存键值对，长度为容量的两倍// 根据 key 的 hash 在 mHashes 的存放位置 index，可以确定键值对在 mArray 的存放位置// key 存放在 index << 1 处，value 存放在 (index << 1) + 1 处@UnsupportedAppUsage(maxTargetSdk = 28)Object[] mArray;// 当前键值对数量@UnsupportedAppUsage(maxTargetSdk = 28)int mSize;private MapCollections<K, V> mCollections;...
}
3.2、构造函数
public final class ArrayMap<K, V> implements Map<K, V> {.../*** 无参构造函数*/public ArrayMap() {this(0, false);}/*** 有参构造函数** @param capacity 容量*/public ArrayMap(int capacity) {this(capacity, false);}/*** 有参构造函数** @param capacity         容量* @param identityHashCode 是否使用 System.identityHashCode(key) 获取 hashcode 值*/public ArrayMap(int capacity, boolean identityHashCode) {mIdentityHashCode = identityHashCode;if (capacity < 0) {// 容量小于 0，创建一个不可变的 ArrayMapmHashes = EMPTY_IMMUTABLE_INTS;mArray = EmptyArray.OBJECT;} else if (capacity == 0) {// 容量等于 0，创建一个空 ArrayMapmHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;} else {// 容量大于 0，根据指定容量初始化 mHashes 和 mArray 数组// 如果容量是 4 或 8 的话，会查看之前是否有缓存的数组，有就使用缓存allocArrays(capacity);}mSize = 0;}/*** 有参构造函数** @param map ArrayMap 集合*/public ArrayMap(android.util.ArrayMap<K, V> map) {this();if (map != null) {putAll(map);}}...
}
3.3、增操作
public final class ArrayMap<K, V> implements Map<K, V> {.../*** 添加元素** @param key   键* @param value 值* @return 如果 key 存在，则返回 oldValue*/public V put(K key, V value) {// key 的 hash 值final int hash;// 下标int index;// 如果 key 为 null，则 hash 值为0if (key == null) {hash = 0;// 寻找 null 的下标index = indexOfNull();} else {// 根据 mIdentityHashCode 取到 hash 值hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();// 根据 hash 值和 key 找到合适的 indexindex = indexOf(key, hash);}// 如果 index>=0，说明是替换（改）操作if (index >= 0) {// 只需要更新 value 不需要更新 key，因为 key 已经存在index = (index << 1) + 1;// 返回旧值final V old = (V) mArray[index];mArray[index] = value;return old;}// index<0，说明是插入操作。对其取反，得到应该插入的下标index = ~index;// 如果需要扩容if (mSize >= mHashes.length) {// 如果容量大于8，则扩容一半// 否则容量大于4，则扩容到8// 否则扩容到4final int n = mSize >= (BASE_SIZE * 2) ? (mSize + (mSize >> 1)): (mSize >= BASE_SIZE ? (BASE_SIZE * 2) : BASE_SIZE);// 临时数组final int[] ohashes = mHashes;final Object[] oarray = mArray;// 分配空间完成扩容allocArrays(n);// 复制临时数组中的数组进新数组if (mHashes.length > 0) {if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);System.arraycopy(oarray, 0, mArray, 0, oarray.length);}// 释放临时数组空间freeArrays(ohashes, oarray, mSize);}// 如果 index 在中间，则需要移动数组，腾出中间的位置if (index < mSize) {if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize - index)+ " to " + (index + 1));System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);}// hash 数组，就按照下标存哈希值mHashes[index] = hash;// array 数组，根据下标，乘以2存 key，乘以2+1存 valuemArray[index << 1] = key;mArray[(index << 1) + 1] = value;mSize++;// 修改 sizereturn null;}/*** 将一个 ArrayMap 集合添加进来** @param array ArrayMap 集合*/public void putAll(ArrayMap<? extends K, ? extends V> array) {final int N = array.mSize;// 确保空间足够存放ensureCapacity(mSize + N);// 如果当前是空集合if (mSize == 0) {if (N > 0) {// 则直接复制覆盖数组内容即可。System.arraycopy(array.mHashes, 0, mHashes, 0, N);System.arraycopy(array.mArray, 0, mArray, 0, N << 1);mSize = N;}} else {// 否则需要一个一个执行插入 put 操作for (int i = 0; i < N; i++) {put(array.keyAt(i), array.valueAt(i));}}}/*** 将一个 Map 集合添加进来** @param map Map 集合*/@Overridepublic void putAll(Map<? extends K, ? extends V> map) {// 确保空间容量足够ensureCapacity(mSize + map.size());for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {// 分别调用单个增方法 addput(entry.getKey(), entry.getValue());}}/*** 扩容操作** @param size 容量大小*/private void allocArrays(final int size) {// 数量<0，构建一个不可变的 ArrayMapif (mHashes == EMPTY_IMMUTABLE_INTS) {throw new UnsupportedOperationException("ArrayMap is immutable");}// 扩容数量是8if (size == (BASE_SIZE * 2)) {synchronized (ArrayMap.class) {// 查看之前是否有缓存的容量为8的 int[] 数组和容量为16的 object[] 数组// 如果有，复用给 mArray mHashesif (mTwiceBaseCache != null) {final Object[] array = mTwiceBaseCache;mArray = array;mTwiceBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];array[0] = array[1] = null;mTwiceBaseCacheSize--;if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes+ " now have " + mTwiceBaseCacheSize + " entries");return;}}} else if (size == BASE_SIZE) {// 扩容数量是4synchronized (ArrayMap.class) {// 查看之前是否有缓存的 容量为4的 int[] 数组和容量为8的 object[] 数组//如果有，复用给 mArray mHashesif (mBaseCache != null) {final Object[] array = mBaseCache;mArray = array;mBaseCache = (Object[]) array[0];mHashes = (int[]) array[1];array[0] = array[1] = null;mBaseCacheSize--;if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes+ " now have " + mBaseCacheSize + " entries");return;}}}// 构建 mHashes 和 mArray，mArray 是 mHashes 的两倍。因为它既要存 key 还要存 valuemHashes = new int[size];mArray = new Object[size << 1];}/*** 确保空间足够存放 minimumCapacity 个数据** @param minimumCapacity 最小容量*/public void ensureCapacity(int minimumCapacity) {// 如果不够扩容if (mHashes.length < minimumCapacity) {// 暂存当前的hash array，后面复制需要final int[] ohashes = mHashes;final Object[] oarray = mArray;// 扩容空间（开头讲过这个函数）allocArrays(minimumCapacity);if (mSize > 0) {// 如果原集合不为空，复制原数据到新数组中System.arraycopy(ohashes, 0, mHashes, 0, mSize);System.arraycopy(oarray, 0, mArray, 0, mSize << 1);}// 释放回收临时暂存数组空间freeArrays(ohashes, oarray, mSize);}}/*** 释放回收临时暂存数组空间** @param hashes 数组* @param array  数组* @param size   长度*/private static void freeArrays(final int[] hashes, final Object[] array, final int size) {// 如果容量是8， 则将 hashes 和array 缓存起来，以便下次使用if (hashes.length == (BASE_SIZE * 2)) {synchronized (ArrayMap.class) {if (mTwiceBaseCacheSize < CACHE_SIZE) {// 0存，前一个缓存的 cachearray[0] = mTwiceBaseCache;// 1存 int[] 数组array[1] = hashes;//2+元素置空，以便 GCfor (int i = (size << 1) - 1; i >= 2; i--) {array[i] = null;}// 更新缓存引用为 arraymTwiceBaseCache = array;// 增加缓存过的 Array 的数量mTwiceBaseCacheSize++;if (DEBUG) Log.d(TAG, "Storing 2x cache " + array+ " now have " + mTwiceBaseCacheSize + " entries");}}// 相同逻辑，只不过缓存的是 int[] 容量为4的数组} else if (hashes.length == BASE_SIZE) {synchronized (ArrayMap.class) {if (mBaseCacheSize < CACHE_SIZE) {array[0] = mBaseCache;array[1] = hashes;for (int i = (size << 1) - 1; i >= 2; i--) {array[i] = null;}mBaseCache = array;mBaseCacheSize++;if (DEBUG) Log.d(TAG, "Storing 1x cache " + array+ " now have " + mBaseCacheSize + " entries");}}}}/*** 返回 key 为 null 的下标 index** @return 返回 key 为 null 的下标 index*/int indexOfNull() {// N 为当前集合 size final int N = mSize;// 如果当前集合是空的，返回~0if (N == 0) {//return ~0;}// 根据 hash 值=0，通过二分查找，查找到目标 indexint index = ContainerHelpers.binarySearch(mHashes, N, 0);// 如果 index<0，则 hash 值=0之前没有存储过数据if (index < 0) {return index;}// 如果 index>=0，说明该 hash 值，之前存储过数据，找到对应的 key，比对 key 是否等于 null。相等的话，返回 index。说明要替换// 关于 array 中对应数据的位置，是 index*2=key，index*2+1=valueif (null == mArray[index << 1]) {return index;}// 以下两个 for 循环是在出现 hash 冲突的情况下，找到正确的 index 的过程：// 从 index+1，遍历到数组末尾，找到 hash 值相等，且 key 相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == 0; end++) {if (null == mArray[end << 1]) return end;}// 从 index-1，遍历到数组头，找到 hash 值相等，且 key 相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {if (null == mArray[i << 1]) return i;}// key 没有找到，返回一个负数。代表应该插入的位置return ~end;}/*** 根据 key 和 key 的 hash 值，返回 index** @param key  键* @param hash hash 值* @return 返回数组下标*/int indexOf(Object key, int hash) {// N 为当前集合 size final int N = mSize;// 如果当前集合是空的，返回~0if (N == 0) {return ~0;}// 根据 hash 值，通过二分查找，查找到目标 indexint index = ContainerHelpers.binarySearch(mHashes, N, hash);// 如果 index<0，说明该 hash 值之前没有存储过数据if (index < 0) {return index;}// 如果 index>=0，说明该 hash 值，之前存储过数据，找到对应的 key，比对 key 是否相等。相等的话，返回 index。说明要替换。if (key.equals(mArray[index << 1])) {return index;}// 以下两个 for 循环是在出现 hash 冲突的情况下，找到正确的 index 的过程：// 从 index+1，遍历到数组末尾，找到 hash 值相等，且 key 相等的位置，返回int end;for (end = index + 1; end < N && mHashes[end] == hash; end++) {if (key.equals(mArray[end << 1])) return end;}// 从 index-1，遍历到数组头，找到 hash 值相等，且 key 相等的位置，返回for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {if (key.equals(mArray[i << 1])) return i;}// key 没有找到，返回一个负数。代表应该插入的位置return ~end;}...
}
3.4、删操作
public final class ArrayMap<K, V> implements Map<K, V> {.../*** 根据 key 删除元素** @param key 键* @return 返回删除的元素，如若不存在则返回 null*/public V remove(Object key) {// 根据 key，找到下标final int index = indexOfKey(key);if (index >= 0) {// 如果 index>=0，说明 key 有对应的元素存在，则去根据下标删除return removeAt(index);}// 否则返回 nullreturn null;}/*** 根据下标删除元素** @param index 数组下标* @return 返回删除后的元素*/public V removeAt(int index) {// 根据 index，得到 valuefinal Object old = mArray[(index << 1) + 1];// 如果之前的集合长度小于等于1，则执行过删除操作后，集合现在就是空的了if (mSize <= 1) {// Now empty.if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");// 释放回收空间freeArrays(mHashes, mArray, mSize);// 置空mHashes = EmptyArray.INT;mArray = EmptyArray.OBJECT;mSize = 0;} else {// 根据元素数量和集合占用的空间情况，判断是否要执行收缩操作// 如果 mHashes 长度大于8，且 集合长度小于当前空间的1/3，则执行一个 shrunk，收缩操作，避免空间的浪费if (mHashes.length > (BASE_SIZE * 2) && mSize < mHashes.length / 3) {// 如果当前集合长度大于8，则n为当前集合长度的1.5倍，否则n为8// n 为收缩后的 mHashes 长度final int n = mSize > (BASE_SIZE * 2) ? (mSize + (mSize >> 1)) : (BASE_SIZE * 2);if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);// 分配新的更小的空间（收缩操作）final int[] ohashes = mHashes;final Object[] oarray = mArray;allocArrays(n);// 删掉一个元素，所以修改集合元素数量mSize--;// 因为执行了收缩操作，所以要将老数据复制到新数组中if (index > 0) {if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");System.arraycopy(ohashes, 0, mHashes, 0, index);System.arraycopy(oarray, 0, mArray, 0, index << 1);}// 在复制的过程中，排除不复制当前要删除的元素即可if (index < mSize) {if (DEBUG) Log.d(TAG, "remove: copy from " + (index + 1) + "-" + mSize+ " to " + index);System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,(mSize - index) << 1);}} else {// 不需要收缩// 修改集合长度mSize--;// 类似 ArrayList，用复制操作去覆盖元素达到删除的目的if (index < mSize) {if (DEBUG) Log.d(TAG, "remove: move " + (index + 1) + "-" + mSize+ " to " + index);System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,(mSize - index) << 1);}// 记得置空，以防内存泄漏mArray[mSize << 1] = null;mArray[(mSize << 1) + 1] = null;}}// 返回删除的值return (V) old;}/*** 删除 Collection 集合中，所有出现的 key** @param collection Collection 集合* @return true 代表删除成功，false 代表删除失败*/public boolean removeAll(Collection<?> collection) {return MapCollections.removeAllHelper(this, collection);}...   
}
  • MapCollections.removeAllHelper() 方法
abstract class MapCollections<K, V> {.../*** 遍历 Collection，调用 Map.remove(key) 去删除元素** @param map* @param collection* @param <K>* @param <V>* @return true 删除成功，false 删除失败*/public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) {int oldSize = map.size();Iterator<?> it = collection.iterator();while (it.hasNext()) {map.remove(it.next());}// 如果元素不等，说明成功删除元素return oldSize != map.size();}...
}
3.5、查操作
public final class ArrayMap<K, V> implements Map<K, V> {.../*** 根据 key 获取 值** @param key 键* @return 返回值*/public V get(Object key) {// 根据 key 去得到 indexfinal int index = indexOfKey(key);// 根据 index*2+1 得到 valuereturn index >= 0 ? (V) mArray[(index << 1) + 1] : null;}/*** 根据 key 获取数组下标** @param key 键* @return 返回数组下标*/public int indexOfKey(Object key) {// 判断 key 是否是 null，并去查询 key 对应的 indexreturn key == null ? indexOfNull(): indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());}...
}

这篇关于ArrayMap 源码解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1010628。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
Java ArrayList扩容机制 （源码解读）

Java ArrayList扩容机制 （源码解读）

结论：初始长度为10，若所需长度小于1.5倍原长度，则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1：数组默认长度         2:这是一个共享的空数组实例，用于明确创建长度为0时的ArrayList ，比如通过 new ArrayList<>(0)，ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL
阅读更多...
如何在Visual Studio中调试.NET源码

如何在Visual Studio中调试.NET源码

今天偶然在看别人代码时，发现在他的代码里使用了Any判断List<T>是否为空。 我一般的做法是先判断是否为null，再判断Count。 看了一下Count的源码如下： 1 [__DynamicallyInvokable]2 public int Count3 {4 [__DynamicallyInvokable]5 get
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
OWASP十大安全漏洞解析

OWASP十大安全漏洞解析

OWASP（开放式Web应用程序安全项目）发布的“十大安全漏洞”列表是Web应用程序安全领域的权威指南，它总结了Web应用程序中最常见、最危险的安全隐患。以下是对OWASP十大安全漏洞的详细解析： 1. 注入漏洞（Injection） 描述：攻击者通过在应用程序的输入数据中插入恶意代码，从而控制应用程序的行为。常见的注入类型包括SQL注入、OS命令注入、LDAP注入等。 影响：可能导致数据泄
阅读更多...
从状态管理到性能优化：全面解析 Android Compose

从状态管理到性能优化：全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动
阅读更多...
Spring 源码解读：自定义实现Bean定义的注册与解析

Spring 源码解读：自定义实现Bean定义的注册与解析

引言 在Spring框架中，Bean的注册与解析是整个依赖注入流程的核心步骤。通过Bean定义，Spring容器知道如何创建、配置和管理每个Bean实例。本篇文章将通过实现一个简化版的Bean定义注册与解析机制，帮助你理解Spring框架背后的设计逻辑。我们还将对比Spring中的BeanDefinition和BeanDefinitionRegistry，以全面掌握Bean注册和解析的核心原理。
阅读更多...
CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 （最大值之和）给定整数序列 a0,⋯,an−1，求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr（其中0≤l≤r<n0≤l≤r<n）表示，对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同，当且仅当下标不同。 例如，当原序列为 [1,2,1,2] 时，要计算子序列 [
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2