- 双指针遍历/滑动窗口
- 快慢指针遍历
1. 双指针遍历/滑动窗口
1.1 双指针遍历适用场景
- 是存在区间的，两个指针，一个指向区间开头，一个指向区间的结尾，区间一般具有一些特征，区间的边界值一般也比较重要（跟题目限制相关，可能是两个边界值求和与目标值进行比较），根据题目要求移动两边的指针。
- 指针的位置也有可能是相邻的，相当于区间在一点点扩张
1.2 Leetcode实例
q3 无重复字符的最长子串
/**
* 使用双指针的思路，
* pointer A 指向区间开始位置
* pointer B 指向区间结束位置
* 区间之中的元素都是独一无二的
*
* pointer B 每次都往后移动一位
* pointer A 根据B所在地方是否有重复，如出现重复的位置在区间之内，若有重复移动到重复位置的下一位，否则不移动
* @param s
* @return
*/
public static int lengthOfLongestSubstringTwo(String s){
if (s.length() <= 1) return s.length();
int maxLen = 0;
//hashmap用来存储所有字母出现的位置
HashMap<Character, Integer> allCharacter = new HashMap<>();
int i=0, j=1;
allCharacter.put(s.charAt(0),0);
while (j<s.length()){
char lastPosChar = s.charAt(j);
if (allCharacter.containsKey(lastPosChar)){
if (allCharacter.get(lastPosChar) >= i){
i = allCharacter.get(lastPosChar) + 1;
}
//i = Math.max(i, allCharacter.get(lastPosChar))+1;
}
allCharacter.put(lastPosChar,j);
maxLen = Math.max(maxLen, j-i+1);
j++;
}
return maxLen;
}
q11 盛最多水的容器
/**
* 容器的容量是由两边挡板的高度以及两个挡板的距离决定的,使用双指针的方法
* 一开始:
* pointer A 指向开头的挡板
* pointer B 指向尾部的挡板
*
* 因为可能会形成更大的容器是高的那个挡板决定的，比较两个pointer指向挡板的位置的挡板的高度，
* 挡板低的那个往区间内部移动一步
*
* 结束条件是pointer A指向超过pointer B的位置
* @param height
* @return
*/
public int maxAreaTwo(int[] height) {
if (height.length <=1) return 0;
int maxArea = 0;
int i=0, j=height.length-1;
while (i<j){
maxArea = Math.max(maxArea, (j-i)*Math.min(height[i],height[j]));
if (height[i]<height[j]){
i++;
}else {
j--;
}
}
return maxArea;
}
q15 三数之和
/**
* 使用双指针的方案
* 先将数组进行排序，保证数组是有序的也有利于去重
*
* 从前往后遍历整个数组，i是从nums数组从左往右所有非重复的数字
* pointer A 指向 i 的下一位
* pointer B 指向 数组的最后一位
*
* pointer移动的条件:
* 如果三个数字加起来等于零的话 pointerA 和 pointerB 分别往区间内部移动一位，这里注意啦需要去重
* 如果三个数字加起来大于零的话 pointerB 往区间内部移动
* 如果三个数字加起来小于零的话 pointerA 往区间内部移动
* @param nums
* @return
*/
public List<List<Integer>> threeSumTwo(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i=0;i<nums.length;i++){
if (i==0 || nums[i-1] != nums[i]){ //第一个字符去重
int k = i+1;
int j = nums.length-1;
while (k<j){
int sum = nums[i]+nums[j]+nums[k];
if (sum == 0){
res.add(Arrays.asList(nums[i],nums[j],nums[k]));
//向区间内部移动，一定得把两边重复的都去掉, 移动到的位置的下一位和当前的值不一样
while (k<j && nums[k+1] == nums[k]){
k++;
}
while (k<j && nums[j-1] == nums[j]){
j--;
}
k++;
j--;
}else if (sum>0){
j--;
}else {
k++;
}
}
}
}
return res;
}
q16 最接近的三数之和
这题基本上上一个题一毛一样，也是遍历了所有值求了所有三个数字的和。若当前求和的值比之前的值更接近目标值，就更新一下差值。
q26 删除排序数组中的重复项
/**
* 使用双指针的方案进行求解
* pointer A 所指向的位置是前面都不重复的数组的最后一个位置
* pointer B 从前往后遍历找到与pointer A最后一位不一致的话就把它放到pointer A的下一位，于此同时pointerA也移动一位
* @param nums
* @return
*/
public int removeDuplicatesTwo(int[] nums) {
if (nums.length<2) return nums.length;
int i=0;
for (int j=1;j<nums.length;j++){
if (nums[j] != nums[i]){
i++;
nums[i] = nums[j];
}
}
return i+1;
}
q42 接雨水
/**
* 使用双指针的方案进行求解
* pointer A指向最开始的挡板
* pointer B指向最末尾的挡板
*
* 当前挡板比较小的那个有机会可以积水
* 例如pointer A指向的挡板比较短，他就有机会可能能积水，
* 但是他也要看他左边有没有比他高的，如果没有，就要更新最左边最高的高度，
* 并且说明当前的这个位置不能积水
*
* 比较更新完一轮后，两个指针中高度比较低的那个可以往区间内部移动
* @param height
* @return
*/
public int trapTwo(int[] height) {
if (height.length<3) return 0;
int area =0;
int leftMax = 0, rightMax = 0;
int i=0, j=height.length-1;
while (i<j){
if (height[i]<height[j]){
if (height[i]>=leftMax){
leftMax =height[i];
}else {
area += leftMax-height[i];
}
i++;
} else {
if (height[j] >= rightMax){
rightMax = height[j];
}else {
area += rightMax - height[j];
}
j--;
}
}
return area;
}
q209 长度最小的子数组
/**
* 使用双指针的方式，区间是要求和的区间
* pointer A 指向区间的开始
* pointer B 指向区间的另一端
*
* 一开始pointer B一直往右移动，直到求和值超过了目标值
* 这个时候就可以让pointer A往右移动，移动到区间的求和值小于目标值，
* 在这个过程中也要更新最小长度
*
* @param s
* @param nums
* @return
*/
public static int minSubArrayLenTwo(int s, int[] nums){
if (nums.length==0||(nums.length==1&&nums[0]<s)) return 0;
if (nums[0]>s) return 1;
int minLen = Integer.MAX_VALUE;
int sum = nums[0];
int i=0;
for (int j=1;j<nums.length;j++){
sum += nums[j];
while (sum >= s){
minLen = Math.min(minLen, j-i+1);
sum -= nums[i];
i++;
}
}
return minLen == Integer.MAX_VALUE ? 0:minLen;
}
以上的题目尝试用双指针的方式进行了求解，但是也有其他的方案，其他的solution可以参考： https://www.jianshu.com/p/d4f54822be8c
2. 快慢指针遍历
2.1 快慢指针遍历的适用场景
快慢指针指的是有两个指针，一个移动的慢一个移动的快。
适用场景：
- 检测链表或者一连串数字中是否有循环
- 返回一个链表中的中间的元素
2.2 Leetcode示例
q141 环形链表
/**
* 使用快慢指针的方式
* 一个指针是快指针，一次走两步，另一个指针是慢指针一次就走一步
* 如果两个指针能碰到说明链表有循环
* @param head
* @return
*/
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null)return false;
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
return true;
}
}
return false;
}
q202 快乐数
/**
* 使用快慢指针的方式，
* 慢指针是挨个按规律求算
* 快指针是步长是2的大小进行增长
* @param n
* @return
*/
public boolean isHappyTwo(int n) {
int slow = n;
int fast = n;
do{
slow = calculateEveryBit(slow);
fast = calculateEveryBit(calculateEveryBit(fast));
}while (slow != fast);
return slow == 1;
}
public static int calculateEveryBit(int n){
int res = 0;
while (n>0){
res += (n%10)*(n%10);
n = n/10;
}
return res;
}
q876 链表的中间节点
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
哈哈哈哈哈，这几道题同理也有别的解决方案，其他的方案可以参考: https://www.jianshu.com/p/ce2dd7f03a32
