双指针技巧总结

我把双指针技巧再分为两类,一类是「快慢指针」,一类是「左右指针」。
前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。

快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。

判定链表中是否含有环

经典解法就是用两个指针,一个跑得快(一次前进两步),一个跑得慢(一次前进一步)。
如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

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

可以看到,当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。

寻找链表的中点


我们还可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置。

寻找链表的倒数第k个元素

我们的思路还是使用快慢指针,让快指针先走 k 步,然后快慢指针开始同速前进。
这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 k 个链表节点。

左右指针的常用算法

左右指针在数组中实际是指两个索引值,一般初始化为 left = 0, right = nums.length - 1。

二分查找

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 搜索区间[0,nums.length-1]
    while(left <= right) {
        int mid = left + (right - left) / 2;//防止整型溢出
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 缩小搜索区间
        else if (nums[mid] > target)
            right = mid - 1; // 缩小搜索区间
    }
    return -1;
} 

前提:nums数组有序。
重要:不要出现 else,而是把三种情况用 else if 写清楚,这样可以清楚地展现所有细节。

两数之和

给定一个有序整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

暴力解法

hash映射

  1. 遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的 key 值
  2. 如果存在则找到了两个值,如果不存在则将当前的 (nums[i],i) 存入map 中,继续遍历直到找到为止

双指针

类似二分查找,通过调节 left 和 right 可以调整 sum 的大小。

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

反转数组

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

反转字符串

滑动窗口算法

最小覆盖子串

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。

示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明:
如果 S 中不存这样的子串,则返回空字符串 ""。
如果 S 中存在这样的子串,我们保证它是唯一的答案。

暴力解法

for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案

滑动窗口

思路如下:

  1. 我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」。
  2. 我们先不断地增加 right 指针扩大窗口 [left, right),直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
  3. 此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right),直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。
  4. 重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

show code

    public String minWindow(String s, String t) {
        char[] tArray = t.toCharArray();
        char[] sArray = s.toCharArray();
        Map<Character,Integer> need = new HashMap();
        for(int i=0;i<tArray.length;i++){
            int count = need.getOrDefault(tArray[i], 0);
            need.put(tArray[i], count + 1);
        }
        Map<Character,Integer> window=new HashMap();
        int left=0,right=0;
        int minLenth = Integer.MAX_VALUE;
        int valid=0;//匹配的字符数量
        int start=0;
        int size = need.keySet().size();
        while(right<sArray.length){
            char c = sArray[right];
            if (need.containsKey(c)) {// 进行窗口内数据的一系列更新
                int count = window.getOrDefault(c, 0);
                window.put(c, count + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            while(valid==size){
                if (right - left+1 < minLenth) {// 在这里更新最小覆盖子串
                    start = left;
                    minLenth = right - left+1;
                }
                char d = sArray[left];// d 是将移出窗口的字符
                left++;// 左移窗口
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
            right++;//右指针右移
        }
        return minLenth==Integer.MAX_VALUE?"":s.substring(start,start+minLenth);
    }

字符串排列

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。

示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

这种题目相当给你一个 S 和一个 T,请问你 S 中是否存在一个子串,包含 T 中所有字符且不包含其他字符?
这道题的解法和最小覆盖子串类似,只需要改变两个地方:
1、本题移动 left 缩小窗口的时机是窗口大小大于 t.size() 时,应为排列嘛,显然长度应该是一样的。
2、当发现 valid == need.size() 时,就说明窗口中就是一个合法的排列,所以立即返回 true。

找所有字母异位词

给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。

说明:
字母异位词指字母相同,但排列不同的字符串。
不考虑答案输出的顺序。

示例:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

这个所谓的字母异位词,不就是排列吗。相当于,输入一个串 S,一个串 T,找到 S 中所有 T 的排列,返回它们的起始索引。和上题一样的!

最长无重复子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

这就是变简单了,连 need 和 valid 都不需要,而且更新窗口内数据也只需要简单的更新计数器 window 即可。
当 window[c] 值大于 1 时,说明窗口中存在重复字符,不符合条件,就该移动 left 缩小窗口了。

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×