双指针算法在数组/链表操作中应用广泛,很多时候,为了完成某个目的,常常需要不断的循环检查数组或是链表,又或者需要拷贝出额外的存贮空间来保存中间结果。在其中的一些情况下,如果能够合理的应用数组双指针,则可以极大的减少算法的时间复杂度和空间复杂度。
根据初始双指针的位置,可以将之分为双头部指针,双尾部指针以及头尾指针.
今天我们就来看几个利用数组双指针算法的例子。
案例1: 给定一个数组,求出索引i和j,使得i和j之间的子串为符合某个特定条件的子串。
这种类型有很多,主要是为了找出符合特定条件的子串,下面是几个特定条件的例子:
1. Sum(i -> j) > k 的最短子数组, k为某常量2. Sum(i -> j) < k 的最长子数组, k为某常量3. Sum(i -> j) = k 且 j - i = ,m 的最子数组, k为某常量4.(j - i)* min(array[i], array[j]) 最大的子数组
以第一道题为例,就是为了找出和大于某个特定常量的最短子数组。
常见的解决方案可以通过找出所有符合条件的子数组,然后根据这些子数组的长度,选出最短的那个。算法的时间复杂度为O(nlogn),空间复杂度为O(n^2)
当然我们也可以利用双头部指针算法,
- 初始索引i和j指向数组头部,计数器maxLength为0.
- 迭代:
- 如果i与j之间的子数组的和大于k,则判断j -i + 1是否小于maxLength,若是,则将maxLength更新为j -i + 1,i++并移向下一组candidate。
- 如果i与j之间的子数组的和小于等于k,则j++。
- 当j到达数组尾部时,结束迭代。
- 在迭代过程中,计算i与j之间子数组的和并不需要每次都重新计算,而是只要相应增量的加上j位置的值或是减去i位置的值即可。
我们将时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码:
public class MinSubArrayLen { public static void main(String[] args) { MinSubArrayLen ms = new MinSubArrayLen(); System.out.println(ms.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3})); } /** * 双指针-双头部算法 * * @param s * @param nums * @return */ public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) return 0; int i = 0; int j = 0; int min = Integer.MAX_VALUE; int sum = nums[0]; while(true) { if (sum < s) { j++; if (j == nums.length) break; sum += nums[j]; } else { min = Math.min(min, j - i + 1); sum -= nums[i]; i++; } } return min == Integer.MAX_VALUE ? 0 : min; }
许多类似的题目(找出符合特定条件的子串)都可以利用这样的算法来解决,区别仅仅是在于初始状态指针的位置。
第四道题目的原题是这样的:
给定 n个非负整数a1,a2,... an, 每个ai代表位置为i,高度为ai的柱子,那么求i和j使得ai到aj所能形成的正方形最大(即(j - i)* min(ai,aj))
这个问题也还是可以通过双指针算法来解决,区别在于指针的初始状态为一头一尾
- 初始索引i和指向数组头部,j指向数组尾部,计数器maxArea为0.
- 迭代:
- 计算当前Area,若大于maxArea则替换。
- 若a[i] < a[j], 则i++, 否则j--。
- 当i与j相遇时,迭代结束。
时间复杂度降低到O(n),空间复杂度为O(1)。 看一下代码:
public class Solution { public int maxArea(int[] height) { int len = height.length, low = 0, high = len -1 ; int maxArea = 0; while (low < high) { maxArea = Math.max(maxArea, (high - low) * Math.min(height[low], height[high])); if (height[low] < height[high]) { int lowbaseline = height[low]; while(true) { if (low >= high || height[low] > lowbaseline) break; low++; } } else { int highbaseline = height[high]; while(true) { if (high <= low || height[high] > highbaseline) break; high--; } } } return maxArea; } }
还有一类问题,它们并没有找出某个特定子串的要求,但是为了达到常量级的空间复杂度,通常也可以使用双指针算法:
5. 将数组拆分为左奇右偶6. 检查链表是否有环7. 快速排序
第五个例子要求找出数组中所有的奇数和偶数,并将奇数放在数组的前端,偶数放在数组的后端。
这个题目其实很简单,但是要想达到常量级的空间复杂度,则要求必须是一个on place的算法,我们也可以利用双指针来做到这一点。
基本的思路其实是和快速排序的partition一致,关于快排的讨论已经很多了,这里不再赘述。 我们看一下快排的partition代码。为了解释算法本身,并没有做任何优化:
public class QuickSort { /** * 取数组的最后一位做为中位数。 * 从开始进行遍历,如果某值小于该中位数,i向前一步走,i与j的数值互换。 * 如果某值大于该中位数,则j++。 * 算法很精巧,始终维持i与j之间正好是所有大于中位数的值。 * * @param array * @param start * @param end * @return */ private int partition(int[] array, int start, int end) { int mediumVal = array[end]; int i = start - 1; for (int j = start; j < end; j++) { if (array[j] <= mediumVal) { i++; exchange(array, i, j); } } exchange(array, i + 1, end); return i + 1; } }
第六个例子实在是经典算法考题,判断一个链表中是否有环,只要用两个指针,一个每次走一步,另一个每次走两步,看足够多的步之后,两个指针是否会相遇即可。同样也不需要额外的存储空间。
这里就总结了关于双指针算法的7种常见使用场景,欢迎大家提供更多的好例子。
相关推荐
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
适用人群:刚接触数据结构与算法 难度:较简单 方法:多看多练,多思考 语言:java
C51学习手册,介绍运算符,算法,数组,指针,结构体,共用体,枚举,
算法没想象中那么难,只要系统学过,算法几乎就等同与脑筋急转弯。 这次,利用双指针算法优雅地实现有序数组地合并。 看完后,你会觉得原来算法这么简单。
C语言快速排序算法,包含数组和指针的实现方法
指针和数组及算法工具.zip
解答C语言中一些算法,一些好的编码,包括数组,指针等和一些难解答的例子
用于比较指针数组和数组指针实现算法的差异,利用函数返回指针实现。 可作为研究C语言指针使用的范例程序。 有源代码和实现结果图。
用于比较指针数组和数组指针实现算法的差异,利用函数返回指针实现。 可作为研究C语言指针使用的范例程序。 有源代码和实现结果图。
双指针 字符串 滑动窗口 4 困难 数组 二分查找 分治算法 5 中等 字符串 动态规划 6 中等 字符串 7 简单 数学 8 中等 字符串 9 简单 数学 10 困难 字符串 动态规划 回溯算法 11 中等 数组 双指针 12 中等 数学 字符串...
c语言的课件 有概述,算法,数据类型,简单程序,选择,循环,数组,函数,预处理,指针,结构体,位运算,文件和常见错误 徐州师范大学计算机科学与技术学院
python算法-双指针问题一、数组合并1. 使用模拟指针和并两个有序数组2.模拟指针说明:二、二分法(折半查找法)1.有序数组的二分法查找2. 二分法说明三、链表(双链表和单链表区别) 一、数组合并 1. 使用模拟指针和...
双指针 17 中等的 20 简单的 21 简单的 22 中号 24 , 中等的 链表和三指针 25 难的 26 简单的 27 简单的 双指针 33 中等的 35 , 简单的 二分查找 46 中等的 47 中等的 56 中等的 在二维数组中排序 66 简单的 70 简单...
双指针 12 整数转罗马数字 中等 数学 贪心 13 罗马数字转整数 简单 数学 14 最长公共前缀 简单 字符串 15 三数之和 中等 数组 双指针 16 最接近的三数之和 中等 数组 双指针 19 删除链表的倒数第N个节点 中等 链表 ...
双指针 滑动窗口 字符串 数组 二分 分治 字符串(中心扩散) 马拉车(待补充) 字符串 数学 数学 字符串 数学 dp 字符串 数组 双指针 数学 字符串 数学 字符串 字符串 数组 双指针 数组 双指针 字符串 回溯 数组 哈希 双...
数组、双指针 中等 015 数组、双指针 中等 016 数组、双指针 中等 017 字符串、回溯算法 中等 018 数组、哈希表、双指针 中等 019 链表、双指针 中等 022 字符串、回溯算法 中等 026 数组、双指针 简单 027 数组、双...
数组相关的算法问题,一般都可以使用双指针完成操作,有异步指针、快慢指针等,其实就是一种升维的思想,通过一个指针访问数组就相当于一维,用两个指针操作数组,就会出现两个数组同时存在的效果,这就是升维的一种...
C语言全套资料 C语言程序设计 C语言算法 C语言课件 C语言顺序程序设计,C语言数组,C语言循环控制,C语言预处理命令,C语言文件操作指针,C语言选择结构程序设计,C语言结构体与共用体,C语言文件操作,C语言函数
用变量地址作为初值时,该变量必须在指针初始化之前已说明过,且变量类型应与指针类型一致。 可以用一个已赋初值的指针去初始化另一 个指针变量。 不要用一个内部 auto 变量去初始化 static 指针。