双指针法

首先给出例题:

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

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

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

思路一：

暴力循环，O(n2)时间复杂度，因为2层循环，肯定会超时

思路二：

上面的思路显然不行，那么我们换一种思路，我们使用双指针，在遍历的时候一次性删除多种可能性即可

定义 A[i][j] 是numbers[i] + numbers[j]

定义 i = 0,j = numbers.size()-1

定义 sum = numbers[i] + numbers[j]

  • sum < target 那么代表 A[0][length] 小于target，由于数组已经排序，那么numbers[i] 是最小的，那么就让numbers[i]变大即可
  • 即 i++ ，那么就排除了A[i]一整行的数据，时间复杂度降低
  • sum > target 那么代表 A[0][length]大于target，numbers[0] 是最小的，我们需要找和更小的两个数，那么我们需要把length减少
  • 即 j-- , 那么就排除了A[j]一整列的数据，时间复杂度降低

可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最 优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r； 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设 在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 (l,r) 之间，又因为不满足条 件时指针必须移动一个，所以最终一定会收敛在 l 和 r。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0;
        int j = numbers.size() - 1;
        while(i < j)
        {
            int sum = numbers[i] + numbers[j];
            if(sum < target){
                i++;
            }else if(sum > target){
                j--;
            }else{
                return vector<int>{i+1,j+1};
            }
        }
        return vector<int>{-1,-1};
    }
};

142. 环形链表 II

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

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

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

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

思路：

这里牵扯到一个很经典的问题，如何判断是否有环？

  • 快慢指针法
    • 指定两个指针，第二个速度是第一个的两倍
    • 如果这个链表不是环状，那么第一个除了在原点和第二个相遇，接下来不可能相遇
    • 如果是环状，那么第二个一定会碰到第一个点
    • 那么反过来，如果两个点相遇，就一定有环
  • 再思考：我们如何判断入环点？
    • 回到上句，我们现在已经判断出有环状，即两个指针重叠
    • 那么我们让快的指针指向远点，然后调整两指针都是一个一个的遍历(速度相等)
    • 当两个点再次相遇的时候，就一定是入环点
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        do{
            if(!fast || !fast->next)    return NULL;
            fast = fast->next->next;
            slow = slow->next;
        }while(fast != slow);
        fast = head;
        while(fast != slow)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

76. 最小覆盖子串

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

即给定两个字符串 S 和 T，求 S 中包含 T 所有字符的最短连续子字符串的长度

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
输入：s = "a", t = "a"
输出："a"

思路：滑动窗口

  • 时间复杂度不得超过O(n)
  • 定义两个指针 l 和 r 从左向右移动，l 的位置一定在 r 的左边
  • 本题使用两个vector数组来映射字符
  • chars 表示每个字符缺少的数量
  • flag 表示每个字符是否在T中存在
class Solution {
public:
    string minWindow(string s, string t) {
        //slip window
        vector<int> chars(128,0);
        vector<bool> flag(128,false);
        //统计涵盖的字符和涵盖字符出现的次数
        for(int i = 0;i < t.size();i++)
        {
            flag[t[i]] = true;
            ++chars[t[i]];
        }
        
        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(r - l + 1 < min_size){
                        min_l = l;
                        min_size = r - l + 1;
                    }
                    //左边l边界往右走,然后判断s[l]是否符合
                    if(flag[s[l]] && ++chars[s[l]] > 0){
                        --cnt;
                    }
                    ++l;
                }
            }
        }
        return min_size > s.size() ? "" : s.substr(min_l,min_size);
    }
};

633. 平方数之和

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

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
输入：c = 3
输出：false

解题思路：暴力 + 剪枝

  • 左指针初始化为0，右指针初始化为 sqrt(c)
  • 让左指针依次遍历即可，这样时间复杂度为O(sqrt(c))，空间复杂度O(1)
class Solution {
public:
    bool judgeSquareSum(int c) {
        if(c < 0)
        return false;
        int left = 0;
        int right = sqrt(c);
        while(left <= right)
        {
            if(left*left == c - right*right){
                return true;
            }else if(c - right*right > left*left){
                left++;
            }else{
                right--;
            }
        }
        return false;
    }
};

680. 验证回文字符串 Ⅱ

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

输入: "aba"
输出: True
输入: "abca"
输出: True
解释: 你可以删除c字符。

解题思路：双指针法

  • 定义一个验证回文串的函数
  • 例如 abca
  • 当a = a ，双指针往中间走, 发现 b != c
  • 那么此时有2种选择，左指针往右/右指针往左
class Solution {
public:
    bool isPalindrome(const string& s,int low,int high){
        for(int i = low,j = high;i < j;++i,--j){
            if(s[i] != s[j])
            return false;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int low = 0,high = s.size() - 1;
        while(low < high){
            char c1 = s[low],c2 = s[high];
            if(c1 == c2){
                ++low;
                --high;
            }else{
                return isPalindrome(s,low,high-1) || isPalindrome(s,low+1,high);
            }
        }
        return true;
    }
};

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

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"
输入:
s = "abpcplea", d = ["a","b","c"]

输出: 
"a"

解题思路：双指针法 + lambda表达式实现自定义排序

  • 首先定义一个函数isSub(string s,string target) ，验证字符串target是否可以由字符串s通过删减得到
  • 定义一个vector，把所有符合定义的字符串放入容器中
  • 然后对容器进行自定义排序，长度优先，长度相等按字符串
class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
        vector<string> res;
        for(int i = 0;i < d.size();i++){
            if(isSub(s,d[i])){
                res.push_back(d[i]);
            }
        }
	    //依据长度/字典序排序
        sort(res.begin(),res.end(),[](const string& a,const string& b){
                if(a.size() < b.size()){
                    return true;
                }else if(a.size() > b.size()){
                    return false;
                }else{
                    return a > b;
                }
            });
        
        if(!res.empty())
        return res[res.size()-1];
        else
        return "";
    }
    //字符串是否符合要求
    bool isSub(string s,string target){
        int i = 0,j = 0;
        while(i < s.size()&&j < target.size()){
            if(s[i] == target[j]){
                j++;
            }
            i++;
        }
        return j == target.size();
    }
};
leetcode
双指针

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

SpringBoot组件学习 Previous
贪心算法 Next