算法题——双指针解法类型题

双指针顾名思义就是通过两个指针来对数组、链表等一些线行数据结果进行遍历来规整出符合题目描述的问题结果，例如通过快慢指针找到链表的中间节点、通过左右夹逼指针找出某个区间的最大值等等。对于哪种类型的题而言是能够采用上指针法来解决的，一般需要满足几个条件：
1、题目本身的数据结构为：数组或者链表这类线性结构
2、题目的问题是：针对数组的某个区间

下面以几个典型的双指针法解题：

• 三数之和

解题：首先要去分析该题如何解决？以往我们一般看到的都是两数之和，直接创建一个哈希表进行查找即可，但是到了三数之和后，发现通过哈希表解决起来难度变大，实现起来考虑情况也变得复杂。那么我们能不能采用固定一个数，然后再然另外两个数再某一个区间里面变动并求和比较大小，之后再根据大小比较的情况继续移动另外两个数。这个思路听起来是比较合适的，也是大家能普遍想到的解决方案，但是其中有个问题，就是两个数的指针应该如何移动并且不会重复？这个解决起来也比较简单，直接对数组进行排序，那么根据三数之和与0之间大小比较，即可移动右区间的另外两个指针，这下思路就比较清晰了，具体代码如下：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 设置双指针
            int j = i + 1, k = len - 1;
            // 作为首尾双指针（主要目的是夹逼，越来越逼近目标值）
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) {
                    j++;
                    while (j < k && nums[j] == nums[j - 1]) j++;
                } else if (sum > 0) {
                    k--;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                } else {
                    list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--; 
                    while (j < k && nums[j] == nums[j - 1]) j++;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                }
            }
        }
        return list;
    }
}

• 原地删除排序数组中的重复项

解题：最经典的双指针类型题，快指针向右移动，并且与满指针对应下标元素进行比较，当不相等时快慢指针同时右移，相等时仅仅快指针右移动。

class Solution {
    public void removeDuplicates(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != nums[left]) {
                nums[++left] = nums[right];
            }
            right++;
        }
        return Arrays。copyOfRange(nums, 0, left + 1);
    }
}

• 接雨水问题：

解题：接雨水问题的关键在于如何找到凹槽部分，当利用双指针解法时左右指针分别从数组的其实下标与终止下标进行区间缩紧，在缩紧过程中需要找到左部分的最大值leftmax以及右部分的最大值rightmax，也就是该容器当前能承受的高度。之后计算遍历当前柱子与max高度之间的差值并求和，最终得到接雨水的容量。

class Solution {
    public int trap(int[] nums) {
        int left = 0, right = nums.length - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;
        while (left < right) {
            if (nums[left] < nums[right]) {
                if (nums[left] > leftMax) {
                    leftMax = nums[left];
                } else {
                    result += leftMax - nums[left];
                }
                left++;
            } else {
                if (nums[right] > rightMax) {
                    rightMax = nums[right];
                } else {
                    result += rightMax - nums[right];
                }
                right++;
            }
        }
        return result;
    }
}

• 快慢指针的常见算法：

  • 判断链表是否有环：

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

  • 寻找链表的中点：

    ListNode findMidNode(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    // 如果链表节点数为奇数，那么slow节点在中间；如果链表节点数为偶数，那么slow节点在偏右侧
    while (fast != null && fast.next != null) {
       fast = fast.next.next;
       slow = slow.next;
    }
    return slow;
    }

  • 反转数组：

    void reverse(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
       int temp = nums[left];
       nums[left++] = nums[right];
       nums[right--] = temp;
    }
    }

  • 滑动窗口算法模板：

    int left = 0, right = 0;
    while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    while (window needs shrink) {
       //缩小窗口
       window.remove(s[left]);
       left++;
    }
    }

    该算法的模板解析，以例题来解决：
    
    解题：该题是一道典型的滑动窗口题，首先移动right右指针满足字符串包括T串中所有字符，之后移动左子串对区间进行压缩；

    class Solution {
    public String minWindow(String s, String t) {
       //哈希表相当于管理窗口的容器
       HashMap<Character, Integer> map = new HashMap<>();
       for (char c : t.toCharArray()) {
           map.put(c, map.getOrDefault(c, 0) + 1);
       }
       String result = "";
       // cnt表示t字符串包含的字符
       int cnt = map.size();
       // 双指针，right右移动
       int left = 0, right = 0;
       while (right < s.length()) {
           char chr = s.charAt(right);
           if (map.containsKey(chr)) {
               map.put(chr, map.get(chr) - 1);
               if (map.get(chr) == 0) {
                   cnt--;
               }
           }
           // 设置窗口缩小条件
           while (cnt == 0) {
               if (result.isEmpty() || result.length() > right - left + 1) {
                   result = s.substring(left, right + 1);
               }
               // left下标如果去除后会带来什么后果
               char crh = s.charAt(left);
               if (map.containsKey(crh)) {
                   if (map.get(crh) == 0) {
                       cnt++;
                   }
                   map.put(crh, map.get(crh) + 1);
               }
               // left指针右移
               left++;
           }
           // right指针右移
           right++;
       }
       return result;
    }
    }