快慢指针的实际应用

青旅半醒 2023-02-18 08:05 187阅读 0赞

### 快慢指针概念 ###

**快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。**

通过一道问题来理解快慢指针：

> 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

先给出图解：P慢指针 C快指针  
![图解][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70]  
附上代码：

public int removeDuplicates(int[] nums) { 
        // 快慢指针 pre慢指针 cur快指针
        int pre = 0, cur = 0, len = nums.length;
        while (cur < len) { 
            if (nums[pre] == nums[cur]) { 
                cur++;
            } else { 
                ++pre;
                // 修改前n项
                nums[pre] = nums[cur];
                cur++;
            }
        }
        return pre + 1;
    }

看过上面图示与代码，相信大家已经对快慢指针有了自己的理解，下面分享一个在实际场景中应用快慢指针解决的问题  
**场景**  
从数据库中查询出所有符合条件的房产，将结果按社区分组后组织成下一个服务需要的参数  
**优化前方案**  
从数据库分组查询出符合条件的社区ID，按社区ID单独查询符合条件的房产后组织结果  
**优化后方案**  
从数据库中查询出所有符合条件的房产，使用快慢指针组织相同社区下的房产  
附上代码：

List<Object> result = new ArrayList<>();	   // 数据库查询符合条件房产结果
    List<NextParam> paramList = new ArrayList<>(); // 下个服务需要的参数
    List<String> houseIds = new ArrayList<>();
    int pre = 0, cur = 0, len = result.size();
    while (cur < len) { 
        if(result.get(pre).getCommunityId().equals(result.get(cur).getCommunityId())) { 
            houseIds.add(result.get(pre).getHouseId()); // 组织相同社区的房产ID
            cur ++;
        } else { 
            pre = cur;
            NextParam nextParam = new NextParam();
            nextParam.setCommunityId(result.get(pre == (len-1) ? pre : pre - 1).getCommunityId());
            nextParam.setHouseIds(houseIds);
            list.add(nextParam);
            houseIds = new ArrayList<>();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616152548761.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MDYzNzg1,size_16,color_FFFFFF,t_70