尺取法(又称为双指针,Two Points)是算法竞赛中一个常用的优化技巧,哟ing来解决序列的区间问题,操作简单,容易编程。如果区间是单调的,也常常用二分法求解,所以很多问题用尺取法和二分法都行。另外,尺取法的操作过程和分治算法的步骤很相似,有时也用在分治中。
双指针技巧再分为两类,一类是「快慢指针」,一类是「左右指针」。
快慢指针:同向扫描,指针i和j方向相同,都从头到尾,速度不同,如让j跑在i前面。“快慢指针”在序列中产生了一个大小可变的“滑动窗口”,有灵活的应用,如寻找区间、数组去重、多指针问题。
左右指针:反向扫描,指针i和j方向相反,i从头到尾,j从尾到头,在中间相会。
双指针常用于解决下面两类问题:
1.分组:元素两两分组。
2.取区间:取满足题意的某个连续区间,比如:取最长的不含重复元素的区间。
