双指针

这类题一般给定序列，我们要做的是如何把所有子串都枚举到。
应用双指针算法，需要保证序列的单调性（这里指得不只是单调递增递减，当一个指针向一个方向移动的时候，另一个指针只能向一个方向移动）
双指针模板：

  1. for (int i = 0, j = 0; i < n; i ++)
  2.     while(j < i && check(j, i)) j++;
  4. for (int i = 0, j = len - 1; i < len ; i ++)
  5.     while(check2(i, j))j--;

LC3无重复字符的最长子串

解题思路

当设定[j, i]为不重复子串的时候，序列[j, i]满足单调性（j，i都是单方向执行，不会返回）
这就符合双指针的思想。
再设定一个HashMap，判断序列中是否有重复的字符，如果有，j指针向前，直到[j, i]是不重复子串
每次去一个最大区间长度值。

代码

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         //同向双指针模板
  4.         HashMap<Character, Integer> heap = new HashMap<>();
  5.         int res = 0;
  6.         //对应的就是check（）函数判断的是 ij双指针之间是否有重复字符，如果有，j++
  7.         for (int i = 0, j = 0; i < s.length(); i ++)
  8.         {
  9.             heap.put(s.charAt(i), heap.getOrDefault(s.charAt(i), 0) + 1);
  10.             while(heap.get(s.charAt(i)) > 1 && j <= i) 
  11.                 heap.put(s.charAt(j), heap.get(s.charAt(j++)) - 1);
  12.             res = Math.max(res, i - j + 1);
  13.         }
  14.         return res;
  15.     }
  16. }

LC633. 平方数之和

解题思路

在两端设置双指针，由于序列是有序的，两端指针都是不会反向移动

代码

  1. class Solution {
  2.     public boolean judgeSquareSum(int c) {
  3.         //这道题的数据范围很大2e9，O(N)已经是极限了
  4.         int sqrt = (int)Math.sqrt((double)c);
  5.         for (int i = 0, j = sqrt; i <= sqrt; i ++)
  6.         {
  7.             while(i * i + j * j > c && j >= 0) j--;
  8.             if ((i * i + j * j)  == c) return true;
  9.         }
  10.         return false;
  11.     }
  12. }

75. 和为S的两个数字

方法1：和上题思路一样

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         //双指针，i左j右。如果数小，i++(i < j),如果i==j，j++；如果走到头，代表没有
  4.         int i = 0, j = nums.length - 1;
  5.         for (; j >= 0; ){
  6.             while (j >= 0 && nums[i]+nums[j] > target) j--;
  7.             if (i < j && nums[i] + nums[j] == target) break;
  8.              i++;
  9.         }
  10.         return new int[]{nums[i], nums[j]};
  11.     }
  12. }

方法2

空间换时间，使用哈希表存放，已经遍历的值。

  1. class Solution {
  2.     public int[] findNumbersWithSum(int[] nums, int target) {
  3.         HashSet<Integer> hash = new HashSet<Integer>();
  4.         int i;
  5.         for (i = 0;i <nums.length; i ++){
  6.             if (hash.contains(target-nums[i])) break;
  7.             hash.add(nums[i]);
  8.         }
  9.         return new int[]{nums[i], target-nums[i]};
  10.     }
  11. }

双指针有序性质76. 和为S的连续正数序列

  1. class Solution {
  2.     public List<List<Integer> > findContinuousSequence(int sum) {
  3.         //双指针,根据有序的特点找到对应的i,j，通过等差数列的性质求出总和
  4.         int i = 1, j = 1;
  5.         List<List<Integer>> res = new ArrayList<List<Integer>>();
  6.         List<Integer> t = new ArrayList<Integer>();
  7.         for (; j < sum;){
  8.             //如果比sum小，需要扩大，就让j++
  9.             while ((i + j) * (j - i + 1)/ 2 < sum) j++;
  10.             if ((i + j)*(j -i + 1)/2 == sum) {
  11.                 for (int x = i; x <= j; x++)    
  12.                     t.add(x);
  13.                 res.add(new ArrayList<Integer>(t));
  14.                 t.clear();
  15.             }
  16.             //如果比sum大，i++;
  17.             i++;
  18.         }
  19.         return res;
  20.     }
  21. }

395. 至少有 K 个重复字符的最长子串

对于普通的双指针来说，ij之间不能满足单调性。

对于i来说，如果i后移，j也可能向前移动。（因为会出现新的字符）

  • 枚举区间最多包含的不同字符的数量，最多只能有26个不同的小写字母。 因此一定会枚举到最优解（最优解中不同字符的数量肯定位于1~26之间）
  • 使用哈希表存放字符和对应出现的数量

  • 同时维护区间内的两个变量：

    • 字符重复数量>=k 的字符数量x
    • 不同字符的数量y
  • 在这种情况下，区间的长度越长，字符重复次数>k的可能性越大

因此双指针有了一个约定条件：区间不超过m个新的字符（0<m<=26）

对于每一个i来说，找到最左边的j，使得ij之间的长度最大

如果i向后移动，达到了限定条件下，j只能向后移动（因为i向后移动不能新增新的字符）

没有达到限定条件，i一直后移。

这样双指针满足了单调性。

当x==y，即区间中所有字符都满足了要求，更新最大长度。最终肯定会枚举到最优解。

时间复杂度双指针 - 图1#card=math&code=o%2826%2An%29)

LC5 最长回文子串

解题思路

当ij对应的字符串不相等的时候，就不是回文子串了
这样ij两个指针都是单一方向移动的，符合双指针的思想
那我们如何保证枚举到所有的子串呢? 这就需要我们把中心位置设定在每个点上
每个点也设置为偶数中心点和奇数中心点…..
这样的话，我是可以看到，会有重复遍历的情况，这个算法O(N^2)还是可以改进的。思路

代码

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         //当ij对应的字符串不相等的时候，就不是回文子串了
  4.         //这样ij两个指针都是单一方向移动的，符合双指针的思想
  5.         //那我们如何保证枚举到所有的子串呢? 这就需要我们把中心位置设定在每个点上
  6.         //每个点也设置为偶数中心点和奇数中心点.....
  7.         //这样的话，我是可以看到，会有重复遍历的情况，这个算法还是可以改进的。
  8.         int len = s.length();
  9.         String ans = new String();
  10.         for (int i = 0; i < len; i ++){
  11.             int l = i, r = i;
  12.             while(l >= 0 && r <= len - 1 && s.charAt(l) == s.charAt(r)){l --; r++;}
  13.             if (ans.length() < r - l - 1)
  14.                 ans = s.substring(l + 1, r);
  16.             l = i; r = i + 1;
  17.             while(l >= 0 && r <= len - 1 && s.charAt(l) == s.charAt(r)){l --; r++;}
  18.             if (ans.length() < r - l - 1)
  19.                 ans = s.substring(l + 1, r);
  20.         }
  21.        return ans;
  22.     }
  23. }

26. 删除有序数组中的重复项

双指针,当快指针和慢指针指向相同的数，快指针跳过这些数(不做处理)
指向不同的数时，把快指针的数赋值给慢指针的下一位（要么是重复的数，要么就是原数据）
这样慢指针就是符合条件的数组尾指针

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         //双指针,当快指针和满指针指向不同的数，满指针移动到快指针的地方
  4.         //如果指向相同的数，说明这个数要删除
  5.         int n = nums.length;
  6.         int j = 0;
  7.         for (int i = 0; i < nums.length; i ++){
  8.             while (j < i && nums[i] != nums[j]) nums[++j] = nums[i];
  9.         }
  10.         return j + 1;
  11.     }
  12. }

80. 删除排序数组中的重复项 II

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         //j就是输出数组的尾端点，i是输入数组的尾端点
  4.         //把符合条件的都放到慢指针的数组里
  5.         //如果nums[j] != nums[i] or nums[i] != nums[j - 1], nums[++j] = nums[i]
  6.         int j = 1;
  7.         for (int i = 2; i < nums.length; i ++)
  8.         {
  9.             if (nums[j] != nums[i] || nums[i] != nums[j - 1]) {
  10.                 nums[++j] = nums[i];
  11.             }
  13.         }
  14.         return j + 1;
  15.     }
  16. }

LC141. 环形链表

解题思路

快慢指针：fast指针每次移动2步，slow每次移动一步。
这样每次迭代，fast都会比slow多移动一步。

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. public class Solution {
  13.     public boolean hasCycle(ListNode head) {
  14.         //首先我们看到这是单向链表，意味着它只能由一个出口，最多只有一个环
  15.         //如果从头节点开始遍历，就意味着一定会进入环
  16.         //定义快慢指针（快指针是慢指针的两倍）。如果两个指针相遇，就是有环
  17.         //如果快指针走到了尾节点，就说明没有环
  18.         ListNode fast = head, slow = head;
  19.         if (fast == null || fast.next == null) return false;
  20.         while(fast != null){
  21.             fast = fast.next; slow = slow.next;
  22.             if (fast == null) return false;
  23.             fast = fast.next;
  24.             if (fast == slow) return true;
  25.         }
  26.         return false;
  27.     }
  28. }

142. 环形链表 II

解题思路

   //我们让快慢指针的初始位置更改，让他们第一次相遇的位置就是入口点
    //位置定在哪里？
    //让慢指针从head开始，它进入入口的时候，快指针也进入入口
    //快指针初始位置在那？我们先看到：假设快慢指针同时在起点，他们最终相遇的位置距离入口是y
    //当慢指针走了x步进入入口，快指针已经在环走了x步。
    //慢指针回退y步，快指针回退2y步。慢指针进入入口的时候，快指针在环-y（== x）的地方
    //如果快指针从y点（相遇点）出发（它此时距离入口就是环-y == x，和慢指针同样的距离），
    //慢指针从head出发，他们最终相遇就是在入口点

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //我们让快慢指针的初始位置更改，让他们第一次相遇的位置就是入口点
        //位置定在哪里？
        //让慢指针从head开始，它进入入口的时候，快指针也进入入口
        //快指针初始位置在那？我们先看到：假设快慢指针同时在起点，他们最终相遇的位置距离入口是y
        //当慢指针走了x步进入入口，快指针已经在环走了x步。
        //慢指针回退y步，快指针回退2y步。慢指针进入入口的时候，快指针在环-y（== x）的地方
        //如果快指针从y点（相遇点）出发（它此时距离入口就是环-y == x，和慢指针同样的距离），
        //慢指针从head出发，他们最终相遇就是在入口点
        ListNode fast = head, slow = head;
        while(fast != null){
            fast = fast.next; slow = slow.next;
            if (fast == null) return null;
            fast = fast.next; 
            if (fast == slow){
                //System.out.println(slow.val);
                slow = head;
                while(fast != slow){
                    fast = fast.next; slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

287. 寻找重复数

解题思路

把下标看成一个点，值作为下一个连接点。
除去起始点0，剩下的n-1个点都有一条出边（其中一个点有两条入边），意味着有一个环。
相当于找环的入口点。
那么就类似于LC142题。找到两个点的相遇点作为快指针的起点。
当快慢指针相遇的时候就是入口点。

代码

class Solution {
    public int findDuplicate(int[] nums) {
     //一定会存在环
        int i = 0, j = 0;
        while(true){
            i = nums[i]; j = nums[j];
            i = nums[i];
            if (i == j) break;
        }
        j = 0;
        while(i != j){
            i = nums[i]; j = nums[j];
        }
    return i;
}
}

38. 外观数列 - 力扣

class Solution {
    public String countAndSay(int n) {
        //循环1~n-1，
        //对每一项，遍历字符串，使用双指针jk求重复的字符(k表示j后第一个不和j相同的字符下标)
        //个数为 k - j，更新string t = tostring k-j + tostring j
        String t = "1"; String res = "";
        if (n == 1) return t;
        while (--n != 0){
            //循环字符串t
            int j = 0, k = 1;
            res = "";
            for (; j < t.length(); j = k){
                while (k < t.length() && t.charAt(j) == t.charAt(k)) k++;
                res += Integer.valueOf(k - j).toString() + t.charAt(j);
            }
            t = res;
        }
        return res;
    }
}

双指针+哈希表76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        //双指针+哈希表
        // hash1记录t中每个字符出现的次数
        // hash2记录s中每个字符从i~j中字符出现的次数
        // cnt记录hash1中的字符在hash2中出现的次数（刨去重复字符）
        // 遍历s字符，如果当前字符个数 hash2[j]+1 <= hash1[j],cnt++，插入hash2
        // 如果 hash2[i] > hash1[i],i++(hash1i当前对应的字符在s中是多余的)
        // 如果cnt >= t.length, 说明hash2中已经包含了hash1中的所有字符
        HashMap<Character, Integer> hash1 = new HashMap<>();
        HashMap<Character, Integer> hash2 = new HashMap<>();
        int len = s.length(); int mini = -1, minj = -1, minv = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 0; i < t.length(); i ++){
            char c = t.charAt(i);
            hash2.put(c, hash2.getOrDefault(c, 0) + 1);
        }
        for (int i = 0, j = 0; j < len; j ++){
            char c = s.charAt(j);
            hash1.put(c, hash1.getOrDefault(c, 0) + 1);
            if (hash2.getOrDefault(c, 0) >= hash1.get(c)) cnt++;
            char ci = ' ';
            while (i <= j && hash1.get(ci = s.charAt(i)) > hash2.getOrDefault(ci, 0)) {
                i++;hash1.put(ci, hash1.get(ci) - 1);
            }
            if (cnt == t.length())
                minv = Math.min(minv, j - i + 1);
            if (minv == j - i + 1){minj = j; mini = i;}
        }
        if (mini == -1 && minj == -1) return "";
        return s.substring(mini, minj + 1);
    }
}

(额外约束条件) 最短无序连续子数组

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        /**
            st:子数组左边界-1 ed:右边界+1
            保证: st <= 子数组中的每一个数  子数组中的每一个数 <= ed
            从左向右遍历,如果是递增,st++
            如果是递减,ed--
            最后长度 ed - st + 1
         */
        int st = 0, ed = nums.length - 1;
        for (int i = 0; i < ed; i ++){
            if (nums[i] <= nums[i + 1]) st++;
            else break;
        }
        for (int i = ed; i > st; i --){
            if (nums[i] >= nums[i - 1]) ed--;
            else break;
        }
        if (st == ed) return 0;
        // 保证st <= 子数组中的每一个数,这里一开始st是左边界,但是肯定会st--一次,--之后,st就表示左边界-1
        for (int i = st + 1; i < nums.length; i ++){
            while (st >= 0 && nums[st] > nums[i]) st--;
        }
        //  子数组中的每一个数 <= ed,ed状态和上同理
        for (int i = ed - 1; i >= 0; i --)
            while (ed < nums.length && nums[ed] < nums[i]) ed++;
        return ed - st - 1;
    }
}

滑动窗口（单调队列）：

单调队列的性质就是任何一个数不会重复地添加到队列中，并且相对与队列中的元素来说，新进队列的元素总是更加具有竞争力的（生存周期更长）。
因此单调队列解决题目的关键在于如何设定进队出队的条件。

if (hh <= tt && check1(i, hh))hh++;
while(hh <= tt && check2(i, tt)) tt--;
q[++tt] = i;

找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        /**
            使用一个双指针(滑动窗口)和一个hash(维护p中每一个字符出现的次数)
            如何快速判断当前维护的子串中和p是否相同?
                记录一个变量cnt:子串中的符合要求(字母次数==p中字母次数)的字母种类数
                如何维护变量?子串中出现一个字符,进行hash的++/--,如果为0,对应cnt++, cnt == n 字符串相等
            用滑动窗口记录子串;cnt表示p当前的种类数; 如果窗口长度>p.size, 指针former移动,同时hash,cnt改变 
            如果cnt == 0,子串和p相等
         */
        HashMap<Character, Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        int n = p.length();
        for (int j = 0; j < n; j ++){
            map.put(p.charAt(j), map.getOrDefault(p.charAt(j), 0) + 1);
        }
        int cnt = 0, total = map.size();
        for (int i = 0, j = 0; j < s.length(); j ++){
            char c = s.charAt(j);
            map.put(c, map.getOrDefault(c, 0) - 1);
            if (map.get(c) == 0) cnt++;
            //维护窗口长度
            if (j - i + 1 > n){
                char c1 = s.charAt(i);
                map.put(c1, map.getOrDefault(c1, 0) + 1);
                // 如果map原来没有，i移动后，出现了这个字符，那么有一个字符种类：p和子串的字符次数不相等，cnt--
                if (map.get(c1) == 1) cnt--;
                i++;
            }
            if (cnt == total) res.add(i);
        } 
        return res;
    }
}