题海战术——双指针

给定一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路分析:

如果所有的数都是非负整数,直接按照原顺序,对数字平方塞入新的数组就是答案

否则:找到负数中下标最大的,令他为i,然后定义令一个指针j=i+1;不断比较i和j对应的数的平方的大小关系,然后选择小的那个塞入新的数组,并且更新指针的位置,知道两个指针都到数组边缘时,结束

输入参数为数组时,如果要判断数组第一个元素的状态,记得对数组判空

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector <int> ans;                             // (1)ans为结果数组,用来存储最终答案
        if (nums.size() == 0) {                       // (2)如果给定数组长度为0,则直接返回空数组
            return ans;
        }
        else if(nums[0] >= 0) {
            for(int i = 0; i < nums.size(); ++i) {    // (3)给定数组所有元素都是非负整数时,直接有序的生成
              //新的数组,数组元素为原数组元素的平方
                ans.push_back(nums[i] * nums[i]);
            }
        }
        else {
            int i, j;
            for(int p = nums.size()-1; p >= 0; --p) {
                if(nums[p] < 0) {
                    i = p;
                    break;                            // (4)找到负数中,下标最大的数,记为i
                }
            }
            j = i + 1;                                // (5)初始化指针j=i+1;

            while(i >= 0 || j < nums.size()) {        // (6)开始对两个指针进行迭代枚举,结束条件是两个指针都
              //碰到数组的边界
                if(i < 0) {                           // (7)左指针退化,左边元素耗尽了
                    ans.push_back(nums[j] * nums[j]);
                    ++j;
                }else if(j >= nums.size()) {          // (8)右指针退化,右边元素耗尽了
                    ans.push_back(nums[i] * nums[i]);
                    --i;
                }else {
                    int i2 = nums[i] * nums[i];
                    int j2 = nums[j] * nums[j];

                    if(i2 < j2) {                     // (9)左右元素都在,需要选择小的那个先进结果数组,然后向外扩展指针
                        ans.push_back(i2);
                        --i;
                    }else {
                        ans.push_back(j2);
                        ++j;
                    }
                }
            }
        }
        return ans;

    }
};

给定一个数组nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

思路分析:
首先定义二个指针i j 初始情况下i=0,j=1;

当 j<n ,有四种情况

nums[i]==0,nums[j]==0;

nums[i]==0,nums[j]<>0;

nums[i]<>0,nums[j]==0;

nums[i]<>0,nums[j]<>0;

循环的结束条件,一定是j>=n,这个时候,结尾全是零

可以用if(x)来判断表达式x是否为真,用if(!x)来判断表达式X是否为假

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        if(nums.size() <= 1) {
            return ;                          // (1)只有一个元素的时候.不需要做任何操作,直接返回
        }
        int i = 0, j = 1;
        while(j < nums.size()) {
            if(!nums[i] && !nums[j]) {        // (2) 
                ++j;                          
            }else if(!nums[i] && nums[j]) {   // (3)
                int tmp = nums[i];          
                nums[i] = nums[j];
                nums[j] = tmp;
                if(++i == j) ++j;             
            }else if(nums[i] && nums[j]) {    // (4)
                ++i, ++j;
            }else if(nums[i] && !nums[j]) {   // (5)
                if(++i == j) ++j;
            }
        }
    }
};

给定一个长度为 n 的字符串 s ，求一个最长的满足所有字符不重复的子串的长度。

思路分析:

无符号整形在进行判断的时候,如果赋值为-1,就有可能导致变成整数最大值导致逻辑错误

class Solution {
    int hash[257];

public:
    int lengthOfLongestSubstring(string s) {
        memset(hash, 0, sizeof(hash));
        int maxLen = 0;
        int i = 0, j = -1;             // (1)代表一开始是空串
        int len = s.length();          // (2)之所以要这么做,是因为s.length()是无符号整形.
        while(j++ < len - 1) {
            ++hash[ s[j] ];            // (3)尝试向右移动右指针
            while(hash[ s[j] ] > 1) {  // (4)合法性判定
                --hash[ s[i] ];        // (5)尝试向右移动左指针
                ++i;
            }
            if(j - i + 1 > maxLen) {   // (6)更新更大合法长度
                maxLen = j - i + 1;
            }
        }
        return maxLen;
    }
};

给定2个字符串s1 s2.判断s2,是否包含s1的排列.

思路分析:

用双指针配合哈希表.首先用一个hash表来记录s1中每个字符的出现次数.然后对s2

进行双指针算法.对于选取的子串,如果能和s1的每个字符的数量完全匹配,就满足了

class Solution {
    int hash[257];//双指针配合哈希表
public:
    bool checkInclusion(string s1, string s2) {//string 是STL中的模板类,可以用来做字符串的各种操作
        memset(hash, 0, sizeof(hash));
        for(int i = 0; i < s1.length(); ++i) {
            ++hash[ s1[i] ];                   // (1)代表一开始是空串
        }
        int len = s2.length();                 // (2)无符号整形,当有最大值出现,没办法进入下面的循环
        int i = 0, j = -1;
        while(j++ < len - 1) {                 // (3)尝试向右移动右指针
            --hash[ s2[j] ];                   // (4)对新加入的字符,进行计数
            while(hash[ s2[j] ] < 0) {         // (5)合法性判定
                ++hash[ s2[i] ];               // (6)尝试向右移动左指针
                ++i;
            }
            if(j - i + 1 == s1.length()) {     // s1=s2
                return true;
            }
        }
        return false;
    }
};

给定一个含有n个正整数的数组和一个正整数.找出该数组中满足其和>=正整数的长度最小的连续子数组.

const int maxn = 1000000;

int minSubArrayLen(int target, int* nums, int numsSize){
    int i = 0, j = -1;                            // (1) 这表示一开始是从一个空数组开始
    int sum = 0;                                  // (2) sum永远等于num[i:j]的和,利用O(1)
    int len = maxn;                               // (3) len用于存储这个最短子数组的长度,默认为大于数组长度即可
    while(++j < numsSize) {                       // (4)右指针必须在数组范围内
        sum += nums[j];
        while(sum >= target) {
            if((j - i + 1) && j - i + 1 < len) {  // (5) 记录一个可行解
                len = j - i + 1;
            }
            sum -= nums[i++];                     // (6) 左区间右移,所以左边的元素需要去掉
            if(i > j) {                           // (7) 又变回空串了跳出循环
                break;
            }
        }
    
    return (len == maxn) ? 0 : len;
}

给定一个正整数数组 nums 和整数 k 。请找出该数组内乘积小于 k 的连续的子数组的个数。

思路分析:

两个指针,都只会增加不会减少

int numSubarrayProductLessThanK(int* nums, int numsSize, int k){
    int i = 0, j = -1;                // (1) 初始化为一个空数组
    int cnt = 0;                      // (2) 存储满足条件的子数组个数
    int prod = 1;                     // (3) 保存枚举到的区间的乘积
    while(++j < numsSize) {           // (4) 确保右区间是小于数组长度的
        prod *= nums[j];              // (5) 每次扩展右区间,就将对应位置的数字乘上
        while(prod >= k) {
            prod /= nums[i++];        // (6) 去掉左区间的值
            if(i > j) {
                break;                // (7) 当这个区间不存在,跳出
            }
        }
        cnt += j - i + 1;             // (8) 满足区间的长度,就代表了总共有多少个
    }
    return cnt;
}

给你一个字符串 s 、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。对于 t 中重复字符，寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。

思路分析:

每次迭代循环移动右指针j,并且执行--hash[s[j]],一旦出现hash[s[j]]=0,表示当前的子字符串

s[i:j] 中完全包含了字符串中的s[j]字符,所以执行cnt自增;

当cnt==needcnt时,通过s[i:j]是一个可行解,记录下标到l,r;

class Solution {
    int hash[256];
public:
    string minWindow(string s, string t) {
        memset(hash, 0, sizeof(hash));          // (1)利用一个哈子数组来标记字符串每个字符出现的次数
        int cnt = 0, needCnt = 0;               // (2)cnt代表要取字符串中某一类字符的出现次数;
      //needCnt  代表字符串不同字符出现的次数
        for(int i = 0; i < t.length(); ++i) {
            if(!hash[ t[i] ]) {
                ++needCnt;
            }
            ++ hash[ t[i] ];
        }
        int i = 0, j = -1;                      // (3)//j  i是二个双指针
        int l = 0, r = -1, ans = 1000000;       // (4)子字符串的左右下标
        int size = s.length();
        
        while(j < size - 1) {
            ++j;                             
            if(--hash[ s[j] ] == 0) {
                ++cnt;
            }
            while(cnt == needCnt) {
                if(j - i + 1 < ans) {        
                    ans = j - i + 1;
                    l = i;
                    r = j;
                }
                if( ++hash[ s[i] ] > 0 ) { 
                    --cnt;
                }
                ++i;
            }
        }
        string ret;
        for(int i = l; i <= r; ++i) {
            ret.push_back(s[i]);
        }
        return ret;
    }
};