leetcode双指针水题题解

392. 判断子序列

思路：定义两个指针分别指向s和t然后判断s和t的字符是否相同，如果相同那么i和j同时++，如果不相同则让t跳过该字符去比较下一个字符，最后如果i已经匹配完了那么就说明s是t的子串。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0,j = 0;
        while(i<s.size() && j<t.size())
        {
            if(s[i]==t[j])
            {
                i++;
                j++;
            }
            else
            {
                j++;
            }
        }
        return i==s.size();
    }
};

541. 反转字符串 II

思路：先定义一个起点指针i和一个计数器count，起点加上计数器小于size就继续，计数，计数到2k就反转前k个字符，然后进入最后判断count计数到最后，也就是最后一个区间不满足2k的时候，判断这个值再k到2k之间还是0，k之间，进行反转。

class Solution {
    
public:
    string reverseStr(string s, int k) {
        int count = 0;
        int i = 0;
        while(i+count<s.size())
        {
            count++;
            if(count==2*k)
            {
                reverse(&s[i],&s[i+k]);
                i += count;
                count = 0;
            }
        }
        if(count>=k && count<2*k)
        {
            reverse(&s[i],&s[i+k]);
        }
        else if(count>0 && count<k)
        {
            reverse(&s[i],&s[i+count]);
        }
        return s;

    }
};

面试题 16.24. 数对和

思路：双指针：定义一个左指针i和右指针j，将数组排序，然后开始如i和j位置之和大于target那么j–若是小于则i++，等于就将这对数放进答案数组。

class Solution {
public:
    vector<vector<int>> pairSums(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        int i = 0,j = nums.size()-1;
        sort(nums.begin(),nums.end());
        while(i<j)
        {
            int n = nums[i]+nums[j];
            if(n>target)
            {
                j--;
            }
            else if(n<target)
            {
                i++;
            }
            else
            {
                ans.push_back({nums[i],nums[j]});
                i++;j--;
            }
        }
        return ans;
    }
};

696. 计数二进制子串

思路：定义一个i指针，不断遍历字符串s，然后一个count记录连续的1或者0出现的个数，然后两个相邻的0和1或 1和0出现次数的较小值就是这两组0和1能组成的最大对数。

class Solution {
public:
    int countBinarySubstrings(string s) {
        int num1 = 0,i = 0;
        int ans = 0,count = 0;
        while(i<s.size())
        {
            count = 0;
            char c = s[i];
            while(i<s.size() && c == s[i])
            {
                count++;
                i++;
            }
            ans+=min(num1,count);
            num1 = count;
        }
        return ans;
    }
};