目录

题目

一、无重复字符的最长子串

二、字符串的排列 

总结

---

 

题目

        LeetCode.3

        LeetCode.567

---

 



 

一、无重复字符的最长子串

1. 解题思路：
   1. 双指针滑动窗口：定义一个左指针和右指针，左指针为子串起始位置，右指针为结束位置。依次递增地枚举子串起始位置，不断移动右指针，同时保证子串无重复字符，移动结束后，得到此起始位置的无重复字符的最长子串。记录这个长度，直到枚举结束，找到最长的长度。
   2. 哈希表：判断是否有重复字符，左指针向右移动时，表中删去一个字符，右指针向右移动时，表中增加一个字符；
2. 代码：

   class Solution {
       public int lengthOfLongestSubstring(String s) {
           int ans = 0, r = -1;
           int n = s.length();
           Set<Character> m = new HashSet<Character>();   //哈希集合，记录每个字符是否出现过
           for(int l = 0; l < n; l++){
               if(l != 0){
                   m.remove(s.charAt(l - 1)); //左指针向右移，移除一个字符
               }
               while(r + 1 < n && !m.contains(s.charAt(r + 1))){
                   m.add(s.charAt(r + 1)); //右指针向右移，增加一个字符
                   r++;
               }
               ans = Math.max(ans, r - l + 1);
           }
           return ans;
       } 
   }
   

复杂度分析：

1. 时间复杂度：O(n)
2. 空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。

---

二、字符串的排列 

1. 解题思路：
   1. 双指针法
      1. 快慢两指针；
      2. 快指针先走n步，然后快慢一起走，直到快指针走到末尾，此时慢指针指向倒数第n个数；
      3. 将1和2对应的数值相加，大于target，指针2向左移，小于，指针1向右移。
2. 代码

   class Solution {
       public ListNode removeNthFromEnd(ListNode head, int n) {
           ListNode slow = head, fast = head;
   
           if(fast.next == null)   
               return null;       //空链表
   
           for(int i = 0; i < n; i++){   
               if(fast.next != null)     //快指针先走n步
                   fast = fast.next;
               else
                   return head.next;     //结点数小于n
           }
   
           while(fast.next != null){    
               fast = fast.next;
               slow = slow.next;
           }
   
           if(slow.next != null)
               slow.next = slow.next.next;
               
           return head;
       }
   }

3. 复杂度分析
   1. 空间复杂度：O(1）
   2. 时间复杂度：O(n)

---

总结