[LeetCode] Two Pointer 题目

MengMa

Longest Substring Without Repeating Characters


思路：max存当前最长的无重复子串长度。HashSet存当前的最长无重复子串里包含的字符。
滑动窗口：

用两个指针访问数组：一个快指针，一个慢指针。
简单记法：快指针 吃 字符，慢指针 吐 字符。

快指针一直往右走，尽可能的把没有出现的字符加入到HashSet里。

当出现了重复字符时，即HashSet中已经包含了当前的fast指向的字符，fast指针 停止。
这时候要进行下列处理：
首先记录当前长度，如果比已有max长，则更新max。
否则slow指针开始吐字符，当charAt(slow)并非重复字符时，slow++，直到停止在charAt(slow) == charAt(fast)
这时候不要忘记再slow++一次。确保窗口里只出现一次charAt(fast)那个字符。

时间 O（n） 空间 O(n)

代码：

1. public class Solution {
   
2.     public int lengthOfLongestSubstring(String s)
   
3.     {
   
4.         if(s == null || s.length() == 0) return 0;
   
5.         HashSet<Character> set = new HashSet<Character>();
   
6.         int max = 0;
   
7.         int slow = 0;
   
8.         int fast = 0;
   
9.         while(fast < s.length())
   
10.         {
    
11.             if(!set.contains(s.charAt(fast)))
    
12.             {
    
13.                 set.add(s.charAt(fast));
    
14.             }
    
15.             else
    
16.             {
    
17.                 max = Math.max(max, fast - slow);
    
18.                 while(s.charAt(slow) != s.charAt(fast))
    
19.                 {
    
20.                     set.remove(s.charAt(slow));
    
21.                     slow ++;
    
22.                 }
    
23.                 slow ++;
    
24.             }
    
25.             fast ++;
    
26.         }
    
27.         max = Math.max(max, fast - slow);
    
28.         return max;
    
29.     }
    
30. }

复制代码

MengMa

Remove Duplicates from Sorted Array
思路：
//

代码：

1. public class Solution {
   
2.     public int removeDuplicates(int[] A) {
   
3.         if(A == null || A.length <= 0) return 0;
   
4.         int index = 0;
   
5.         for(int i = 0; i < A.length; i++)
   
6.         {
   
7.            while(i != A.length -1 && A[i + 1] == A【i】) i++;
   
8.            A[index++] = A【i】;
   
9.         }
   
10.         return index;
    
11.     }
    
12. }

复制代码

MengMa

Remove Duplicates from Sorted Array II
allowDups 的意思是表示当前情况下是否允许 重复元素。
时间O（n） 空间O（1）

1. public class Solution {
   
2.     public int removeDuplicates(int[] A) {
   
3.         int len = A.length;
   
4.         if(A==null) return 0;
   
5.         if(len == 0 || len == 1 || len ==2) return len;
   
6.         int index = 1;
   
7.         int prevElem = A[0];
   
8.         boolean allowDups = true;
   
9.         for(int i = 1; i < len; i++)
   
10.         {
    
11.             if(A【i】 == prevElem)
    
12.             {
    
13.                 if(allowDups == true)
    
14.                 {
    
15.                     A[index ++] = prevElem;
    
16.                     allowDups = false;
    
17.                 }
    
18.                 else
    
19.                     continue;
    
20.             }
    
21.             else
    
22.             {
    
23.                 A[index++] = A【i】;
    
24.                 prevElem = A【i】;
    
25.                 allowDups = true;
    
26.             }
    
27.         }
    
28.         return index;
    
29.     }
    
30. }

复制代码