广元网站建设公司,公路水运建设质量与安全监督系统网站,漳州网站建设喊博大科技,结婚证制作生成器app双指针法的核心思想是通过同时操作两个指针来遍历数据结构#xff0c;通常是数组或链表#xff0c;以达到优化算法性能的目的。具体来说#xff0c;双指针法能够减少时间复杂度、空间复杂度#xff0c;或者简化逻辑结构。以下是双指针法的几个核心思想#xff1a; ps 下面…双指针法的核心思想是通过同时操作两个指针来遍历数据结构通常是数组或链表以达到优化算法性能的目的。具体来说双指针法能够减少时间复杂度、空间复杂度或者简化逻辑结构。以下是双指针法的几个核心思想 ps 下面提到的“应用场景”在力扣中都有原题
两端逼近
核心思想通过设置两个指针一个从数据结构的左端开始一个从右端开始然后根据一定的条件向中间移动这两个指针从而逐步缩小问题的规模。应用场景如数组中的“二分搜索”、“盛水最多的容器Container with Most Water”、以及“接雨水Trapping Rain Water”等问题。优势避免了多次嵌套循环或者重复遍历从而将时间复杂度从 O(n^2) 降到 O(n)。
快慢指针
核心思想设置两个指针一个指针每次移动一步慢指针另一个指针每次移动两步或更多快指针。通过这种方式可以在一次遍历中同时完成多项任务。应用场景如链表中的“环检测Cycle Detection”问题、寻找链表的中间节点等。优势通过一次遍历同时获取多种信息提高了效率。
滑动窗口
核心思想使用两个指针定义一个窗口窗口可以向前滑动以覆盖不同的子区间。这种方法常用于解决涉及子数组或子字符串的问题如“最长子串”、“最小覆盖子串”等。应用场景如“最小覆盖子串Minimum Window Substring”、“无重复字符的最长子串Longest Substring Without Repeating Characters”等。优势在处理连续子区间问题时可以在 O(n) 时间复杂度内完成解决方案。
分割与合并
核心思想将问题分解为左右两部分通过双指针分别处理这两部分并在合适的时候合并结果。应用场景如“归并排序Merge Sort”、“两个有序数组的合并”等。 优势可以有效处理有序数组或链表的合并问题保证合并后的结果依然有序。
条件判断与指针移动
核心思想通过条件判断决定哪个指针移动以逐步逼近或找到符合条件的解。应用场景如“二分查找”、“两数之和Two Sum”问题。优势能够快速收敛到问题的解避免不必要的遍历和计算。
总结
双指针法的核心在于利用两个指针的协作通过合理的移动策略来减少问题的规模或提高问题的求解效率。其应用非常广泛可以显著优化涉及数组、链表等线性结构的问题尤其在需要高效处理子区间、子序列、或寻找特定条件下的元素时尤为有效。
这种方法的优势在于线性遍历能够在保持结果正确性的同时减少算法的复杂度是处理各种线性问题时的一个非常有力的工具。
例题力扣接雨水接雨水 双指针代码详细注释
重点1利用双指针的好处就是自然完成遍历两个指针相交就便利完成重点2按列来计算
class Solution {
public:int trap(vectorint height) {// 获取数组的长度int n height.size();// 如果数组为空则没有可以积水的地方直接返回0if (n 0) return 0;// 初始化两个指针分别指向数组的两端int left 0, right n - 1;// 初始化左边和右边的最大高度int leftMax 0, rightMax 0;// 初始化结果存储最终的积水量int waterTrapped 0;// 当左指针小于右指针时继续循环while (left right) {// 如果左边的高度小于右边的高度则说明左边可以计算水洼if (height[left] height[right]) {// 如果当前左边的高度大于或等于leftMax则更新leftMaxif (height[left] leftMax) {leftMax height[left];} else {// 否则则必定形成小水洼计算当前左边位置能存储的水量并累加到waterTrapped中waterTrapped leftMax - height[left];}// 左指针向右移动left;} else {// 如果右边的高度小于或等于左边的高度if (height[right] rightMax) {// 如果当前右边的高度大于或等于rightMax则更新rightMaxrightMax height[right];} else {// 否则计算当前右边位置能存储的水量并累加到waterTrapped中waterTrapped rightMax - height[right];}// 右指针向左移动right--;}}// 返回计算得到的总积水量return waterTrapped;}
};
