双指针到滑动窗口

双指针到滑动窗口算法

1、判定链表中是否含有环

解析:定义两个指针，一快一慢。如果有环，则会相遇。

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

2、已知链表中含有环，返回这个环的起始位置

解析: 快指针走了2k步，慢指针走了k步。多的k步就是环的长度。假设相遇点距离环起始位置m步，则环入口距离初始位置k-m步，相遇点再走k-m步也能到环入口。所以慢指针指向head，快指针指向相遇点，同时前进就能到环的起始位置。

ListNode deleteCycle(ListNode head){
 ListNode fast,slow;
 fast=slow=head; 
while(fast != null&&fast.next!=null){ 
fast = fast.next.next;//快 
slow = slow.next;//慢
 if(fast == slow)
 break; 
} 
slow=head;
 while(slow != fast){
 fast=fast.next; 
slow=slow.next; 
} 
return slow; 
} 

3两数之和。

例子:

n=[2,7,11,5],target = 9 输出:[1,2] 

解析:

int twoSum(int nums[],int target){ 
int left = 0,right = nums.length - 1; 
while(left  right){ 
int sum = nums[left] + nums[right];
 if(target == sum){ 
return new int[]{
left +1,right+1};
 }
else if(target>sum){
 right--; 
}
else if(target  sum){ 
left++;
 } 
} 
return new int[]{-1,-1};
 } 

4反转数组

例子:

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

5无重复字符的最长子串

例子:

输入: "abcabcbb" 输出: 3 

解析:start先不动，用end去搜索，搜索到已经存在的字符则让start指向前面重复字符的下一位。每一轮更新ans，取最大

class Solution { 
    public int lengthOfLongestSubstring(String s) {
         int n = s.length(), ans = 0;
         MapCharacter, Integer> map = new HashMap>();//map的key值若已经存在，则更新value值 
        for (int end = 0, start = 0; end  n; end++) { 
            char alpha = s.charAt(end); 
                if (map.containsKey(alpha)) {
             start = Math.max(map.get(alpha), start);//让start指到alpha的后面 
}
       ans = Math.max(ans, end - start + 1);//最大窗口
       map.put(s.charAt(end), end + 1); 
}
     return ans;
 } } 

最小覆盖子串

例子:

输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 

解析:

public String minWindow(String s, String t) {
     MapCharacter, Integer> map = new HashMap>(); //遍历字符串 t，初始化每个字母的次数
         for (int i = 0; i  t.length(); i++) {
         char char_i = t.charAt(i); 
        map.put(char_i, map.getOrDefault(char_i, 0) + 1); 
}
     int left = 0; //左指针
     int right = 0; //右指针 
     int ans_left = 0; //保存最小窗口的左边界
     int ans_right = -1; //保存最小窗口的右边界 
     int ans_len = Integer.MAX_VALUE; //当前最小窗口的长度 
    //遍历字符串 s
     while (right < s.length()) {
         char char_right = s.charAt(right); //判断 map 中是否含有当前字母
         if (map.containsKey(char_right)) { //当前的字母次数减一 
         map.put(char_right, map.get(char_right) - 1); //开始移动左指针，减小窗口 
         while (match(map)) { //如果当前窗口包含所有字母，就进入循环 
            //当前窗口大小
             int temp_len = right - left + 1; //如果当前窗口更小，则更新相应变量
             if (temp_len  ans_len) {
             ans_left = left;
             ans_right = right;
             ans_len = temp_len; 
           } 
           //得到左指针的字母
          char key = s.charAt(left); 
          //判断 map 中是否有当前字母 
          if (map.containsKey(key)) { 
          //因为要把当前字母移除，所有相应次数要加 1
          map.put(key, map.get(key) + 1);
          } 
         left++; //左指针右移
  }
     } 
        //右指针右移扩大窗口
      right++;
 } 
    return s.substring(ans_left, ans_right+1); 
} 
//判断所有的 value 是否为 0 
    private boolean match(MapCharacter, Integer> map) { 
        for (Integer value : map.values()) { 
            if (value > 0) {
     return false; 
}
 } 
    return true; 
}