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

双指针扫描使用简述

news 2025/9/5 9:33:47

概述

业务中有时会遇到一些稍复杂的校验；
比如比较2个对象数组之间对象的时间属性是否有重叠；
简单操作的话直接嵌套冒泡(O(n^2))就完事了；
但其实可以更优，使用双指针扫描比较，这样时间复杂度仅为O(n)

嵌套冒泡就不上demo了，两个for的事情

上demo

这里的场景是比较2个对象数组之间对象的时间属性的时间区间是否有重叠；

附上手写分析

在这里插入图片描述

   Map<String, List<AsBusinessSuspension>> dataMap = dataList.stream().collect(Collectors.groupingBy(AsBusinessSuspension::getBusinessType));Set<String> businessTypeSet = dataMap.keySet();if(//同时存在库存停用和库存更新!businessTypeSet.contains(AsBusinessSuspensionConstant.INV_UPDATE_STOP)|| !businessTypeSet.contains(AsBusinessSuspensionConstant.INV_UPDATE_ZERO)) return;List<AsBusinessSuspension> updateStopList = dataMap.get(AsBusinessSuspensionConstant.INV_UPDATE_STOP);List<AsBusinessSuspension> updateZeroList = dataMap.get(AsBusinessSuspensionConstant.INV_UPDATE_ZERO);//先按开始时间排序CollectionUtil.sort(updateStopList, Comparator.comparing(AsBusinessSuspension::getBusinessStartTime));CollectionUtil.sort(updateZeroList, Comparator.comparing(AsBusinessSuspension::getBusinessStartTime));int updateStopSize = updateStopList.size();int updateZeroSize = updateZeroList.size();int updateStopIndex = 0;int updateZeroIndex = 0;//双向扫描while (updateStopIndex < updateStopSize && updateZeroIndex < updateZeroSize) {AsBusinessSuspension updateStop = updateStopList.get(updateStopIndex);AsBusinessSuspension updateZero = updateZeroList.get(updateZeroIndex);// stop在zero之前，无交叉，则updateStopIndex指针右移,扫描下一个updateStop元素if (DateUtil.compare(updateStop.getBusinessEndTime(), updateZero.getBusinessStartTime()) <= 0) {updateStopIndex ++;continue;}// zero在stop之前，无交叉，则updateZeroIndex指针右移,扫描下一个updateZero元素if (DateUtil.compare(updateZero.getBusinessEndTime(), updateStop.getBusinessStartTime()) <= 0) {updateZeroIndex ++;continue;}throw new ServiceException(MessageFormat.format("【{0}时间区间{1}】与【{2}时间区间{3}】有重叠",AsBusinessSuspensionConstant.getBusinessTypeDes(updateStop.getBusinessType()),String.join(StrPool.DASHED,DateUtil.format(updateStop.getBusinessStartTime(), DatePattern.NORM_DATETIME_PATTERN),DateUtil.format(updateStop.getBusinessEndTime(), DatePattern.NORM_DATETIME_PATTERN)),AsBusinessSuspensionConstant.getBusinessTypeDes(updateZero.getBusinessType()),String.join(StrPool.DASHED,DateUtil.format(updateZero.getBusinessStartTime(), DatePattern.NORM_DATETIME_PATTERN),DateUtil.format(updateZero.getBusinessEndTime(), DatePattern.NORM_DATETIME_PATTERN))));}