算法（Java）——双指针

算法相关数据结构总结：

序号	数据结构	文章
1	动态规划	动态规划之背包问题——01背包动态规划之背包问题——完全背包动态规划之打家劫舍系列问题动态规划之股票买卖系列问题动态规划之子序列问题算法（Java）——动态规划
2	数组	算法分析之数组问题
3	链表	算法分析之链表问题算法（Java）——链表
4	二叉树	算法分析之二叉树算法分析之二叉树遍历算法分析之二叉树常见问题算法（Java）——二叉树
5	哈希表	算法分析之哈希表算法（Java）——HashMap、HashSet、ArrayList
6	字符串	算法分析之字符串算法（Java）——字符串String
7	栈和队列	算法分析之栈和队列算法（Java）——栈、队列、堆
8	贪心算法	算法分析之贪心算法
9	回溯	Java实现回溯算法入门（排列+组合+子集） Java实现回溯算法进阶（搜索）
10	二分查找	算法（Java）——二分法查找
11	双指针、滑动窗口	算法（Java）——双指针算法分析之滑动窗口类问题

算法中双指针主要包括首尾双指针（对撞双指针），快慢双指针；通过指针的移动解决问题。

数组或字符串相关的问题经常需要运用双指针来求解。而双指针又分为快慢指针和左右指针。
其中快慢指针主要用于解决链表问题，而首尾指针用于解决数组问题。

文章目录

1. 快慢双指针

顾名思义，快慢指针是指一个指针走的快，一个指针走得慢。

1）剑指offer22：链表中倒数第k个节点

算法（Java）——链表中，通过快慢双指针求链表中倒数第k个节点。
题目：输入一个链表，输出该链表中倒数第k个节点。

解题思路：快慢指针，先让快指针走k步，然后两个指针同时走，当快指针到头时，慢指针就是链表倒数第k个节点。
使用双指针可以不用统计链表长度。

初始化：前指针，后指针，双指针都指向头节点head
构建双指针距离：前指针先向前走k步
双指针同时移动：循环，直到前指针到尾节点跳出，后指针指向倒数第k个节点
返回值：返回后指针即可
算法代码：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null||k<=0)
        {
            return null;
        }
        //定义两个指针节点
        ListNode pre=head;
        ListNode last=head;
        //先将一个节点往后移动k-1个距离
        while(pre!=null && k>0){
            pre=pre.next;
            k--;
        }  
        //一起移动，第一个节点移动到末尾，第二个结点移动到倒数第k个节点
        while(pre!=null)
        {
            pre=pre.next;
            last=last.next;
        }
        return last;
    }
}

2）判断链表是否有环

思路：快指针每次走两步，慢指针每次走一步。如果链表中存在环，总有那么一个时刻快指针比慢指针多走了一圈，此时他们相遇。

boolean hasCycle(ListNode head){
  ListNode fast, slow;
  fast = slow = head;
  while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
    if(slow == fast){
      return true;
    }
  }
  return false;
}

2. 首尾双指针

又称对撞双指针，左右双指针。指双指针中一个指针在数组的最左侧，而另一个在最右侧。通过判断，可以分别让两侧的指针向中间移动，以求解问题。

1）剑指offer57：和为s的两个数字

题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

解题思路：首尾双指针，判断两数的和与target进行比较，往中间移动。

算法代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i=0, j=nums.length-1;
        while(i<j){
            int s=nums[i]+nums[j];
            if(s<target) i++;
            else if(s>target) j--;
            else return new int[] {nums[i], nums[j]};
        }
        return new int[0];
    }
}

2）剑指offer21：调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

解题思路：首尾双指针，left右移直到指偶数，right左移直到指奇数，交换。

算法代码：

class Solution {
    public int[] exchange(int[] nums) {
        int left=0,right=nums.length-1;
        int tmp;
        while(left<right){
            if(nums[left]%2==1) left++;
            else if(nums[right]%2==0) right--;
            else{
            tmp=nums[left];
            nums[left]=nums[right];
            nums[right]=tmp;
            left++;
            right--;
            }
        }
        return nums;
    }
}

3. 滑动窗口（双指针）

滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。

滑动窗口的左右界就可以看作双指针处理。

1）剑指offer57_Ⅱ：和为s的连续正数序列

题目：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路：
用滑动窗口解决这个问题时，考虑窗口何时扩大，何时缩小

初始化：左边界i=1，右边界j=2，元素和s=3，结果列表res；
循环：当i≥j时跳出
当s>target时：向右移动左边界i=i+1，并更新元素和s；
当s<target时：向右移动右边界j=j+1，并更新元素和s；
当s=target时：记录连续整数序列，并向右移动左边界i=i+1；
返回值：返回结果列表res；

算法代码：

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i=1,j=2,s=3;
        List<int[]> res = new ArrayList<>();
        while(i<j){
            if(s==target){
                int[] ans = new int[j-i+1];
                for(int k=i; k<=j; k++){
                    ans[k-i]=k;
                }
                res.add(ans);
            }
            if(s>=target){ //与s=target合并
                s-=i;
                i++;
            }else{
                j++;
                s+=j;
            }
        }
        return res.toArray(new int[0][]);
    }
}