双指针刷题–快慢指针与滑动窗口–算法学习（二）

​

算法解释：

双指针主要用来遍历数组，两个指针指向不同的元素，从而协同完成任务。

如果两个指针指向同一个数组，遍历的方向相同且不相交，则也称为滑动窗口。

若两个指针指向同一个数组，但是遍历方向相反，则可以用来快速搜索。

LeetCode题目：

167. 两数之和 II – 输入有序数组

难度简单580

给定一个已按照

非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值

。

numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
复制代码

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
复制代码

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
复制代码

AC代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int start=0,end=numbers.size()-1;

 while(1){
           if(numbers[start]+numbers[end]==target) {
                break;
            }
            else if(numbers[start]+numbers[end]>target){
                end--;
            }
            else if(numbers[start]+numbers[end]<target){
                start++;
            }
        }
        return vector<int> {start+1,end+1};
    }
};
复制代码

思路：

我们已知这个数组是非递减数组，所以arr[i+1]>=arr[i];我们以第一个和最后一个来取平均值，一旦这个值小于目标，就让第一个数变成第二个数，控制减少；一旦大于目标，就使最后一个数变成倒数第二个，来控制减少。

88. 合并两个有序数组

难度简单1086

给你两个按 非递减顺序 排列的整数数组 nums1

和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2

到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
复制代码

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
复制代码

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
复制代码

AC代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[pos--] = nums1[m] > nums2[n]? nums1[m--]: nums2[n--];
        }
        while (n >= 0) {
            nums1[pos--] = nums2[n--];
        }
    }
};
复制代码

思路：

已知这个功能函数的结果是作用在nums1数组上的，所以，我们用一个指针从nums1最后一个元素开始控制。再分别通过nums1和nums2的长度作为指针比较然后进行排序。

这时有特殊情况存在：1、nums1的m为0，nums2里面有数，所以要使用第二个情况下的while来控制没有m的情况，使得nums1能够赋值nums2。

2、nums1中有元素，而nums2中无，则无需操作。

142. 环形链表 II

难度中等

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

**说明：**不允许修改给定的链表。

进阶：

• 你是否可以使用 O(1) 空间解决此题？

示例 1：

​

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
复制代码

示例 2：

​

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
复制代码

示例 3：

​

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
复制代码

AC代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast =head;
        ListNode *slow =head;
        
       do{
            if(!fast||!fast->next)
            return nullptr;
            fast=fast->next->next;
            slow=slow->next;
        } while(fast!=slow);
        fast=head;
        while(fast!=slow){
            if(!fast||!fast->next)
            return nullptr;
            fast=fast->next;
            slow=slow->next;
        }
           
            return fast;
    }
};
复制代码

思路：

对于链表找通路问题，有一个通用的套路，也就是快慢指针，给定两个指针，一个为fast一个为slow，同时从链表开头出发，fast一次走两步，slow一次走一步，直到两指针相遇，如果fast最后指向null，则无通路；当两指针相遇，使fast重新指向链表开头，两指针同时出发，都是每次走一步，直到两指针再次相遇，这个节点就是通路的开始点。

76. 最小覆盖子串

难度困难1336

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
复制代码

示例 2：

输入：s = "a", t = "a"
输出："a"
复制代码

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
复制代码

AC代码：

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> chars(128, 0);
        vector<bool> flag(128, false);
        for(int i=0;i<t.size();i++){
            chars[t[i]]++;
            flag[t[i]]=true;
        }
        int cnt = 0, l = 0, min_l = 0, min_size = s.size() + 1;
        for(int r=0;r<s.size();r++){
            if(flag[s[r]]){
                if(--chars[s[r]]>=0){
                    cnt++;
                }
            }
            while(cnt==t.size()){
                if(min_size>r-l+1){
                    min_size=r-l+1;
                    min_l=l;
                }
                if(flag[s[l]]&& ++chars[s[l]] > 0){
                    --cnt;
                }
                ++l;
            }
        }
        return min_size > s.size()? "": s.substr(min_l, min_size);
    }
};
复制代码

思路：

这题使用滑动窗口求解，就是说什么意思，先固定l在最左边，然后让r往后走，当找齐t中的字母后，会判断l代表的字母是不是在t中且唯一，若不是，那么就使l往右移，使得结果更短。

如果l走到t中的一个唯一字母，那么使得cnt–，重新char++，再让r往后查找，直到再次找到这个字母，这个代码会不断刷新最短记录。

633. 平方数之和

难度中等305

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
复制代码

示例 2：

输入：c = 3
输出：false
复制代码

示例 3：

输入：c = 4
输出：true
复制代码

示例 4：

输入：c = 2
输出：true
复制代码

示例 5：

输入：c = 1
输出：true
复制代码

AC代码：

class Solution {
public:
    bool judgeSquareSum(long c) {
        long start=0,end=sqrt(c);
        while(1){
        if(start*start+end*end==c){
            return true;
        }
        else if(start*start+end*end<c){
            start++;
        }
        else if(start*start+end*end>c&&end>=start){
            end--;
        }
        else if(start*start+end*end>c&&end<start){
            return false;
        }
    }
    }
};
复制代码

思路：

首先明确我们要找的是平方和，所以两个数里面最大的应该是输入数的平方根，而另一个数应该是0，因为只有这样，像1、4、9这样的可整平方根的数能够快速得出true。然后我们判断平方和大小，小了就使start++，大了且end>start则end–，思路清晰，简单一题。

​

680. 验证回文字符串 Ⅱ

难度简单393

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: s = "aba"
输出: true
复制代码

示例 2:

输入: s = "abca"
输出: true
解释: 你可以删除c字符。
复制代码

示例 3:

输入: s = "abc"
输出: false
复制代码

AC代码：

class Solution {
public:
    bool validPalindrome(string s) {
        int start=0,end=s.size()-1;
        while(start<end){
            if(s[start]!=s[end]){
                return check(s,start+1,end)||check(s,start,end-1);
            }
                 ++start;
                 --end;
        }
        return true;
    }
    bool check(string s , int start ,int end){
        while(start<end){
            if(s[start]!=s[end]){
                return false;
            }
                 ++start;
                 --end;
        }
        return true;
    }

   
};
复制代码

思路：

对于这种只能改一次的回文字符串，当第一次发现不回文的时候，就分别对单独删掉双方的情况重新进行回文检查，如果再次出现不回文，则返回false，反之，返回true。

524. 通过删除字母匹配到字典里最长单词

难度中等

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"
复制代码

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"
复制代码

AC代码：

class Solution 
{
private:
    bool isZichuan(string target, string s)
    {
        int t1=0,s1=0;
        while(s1<s.size()&&t1<target.size()){
            if(target[t1]==s[s1]){
                t1++;
            }
                s1++;
        }
        return t1==target.size();
    }
    

public:

    string findLongestWord(string s, vector<string>& d) 
    {
        string inp="";
        for(int i=0;i<d.size();i++){
            if(s.size()<d[i].size()||inp.size()>d[i].size()||(inp.size()==d[i].size()&&inp.compare(d[i]) <0)){
                continue;
            }
            
            if(isZichuan(d[i],s)){
                inp=d[i];
            }
        }
        return inp;
    }
};
复制代码

思路：

这题的条件比较多，只有合适的候选字符串才能进入到数组进行操作，到了isZichuan函数中时，就利用双指针快速进行验证。

今天的算法习题就这么多，我们主要利用了双指针来快速查找，还用了快慢指针解决闭路问题，利用滑动窗口完成贪心策略。

​