Skip to main content

2-双指针-滑动窗口

双指针​

27. 移除元素​

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0, fast = 0;
        while(fast < nums.size())
        {
            if(nums[fast] != val) nums[slow++] = nums[fast];
            fast++;
        }
        nums.resize(slow);
        return nums.size();
    }
};

26. 删除有序数组中的重复项​

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() < 2) return nums.size();
        int left = 1, right = 1;
        while(right < nums.size())
        {
            if(nums[right] != nums[right-1]) nums[left++] = nums[right];
            right++;
        }
        nums.resize(left);
        return nums.size();
    }
};

283. 移动零​

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int fast = 0 ,slow = 0;
        for (; fast < nums.size(); ++fast) {
            if (0!=nums[fast]) nums[slow++] = nums[fast];
        }
        for (int i = slow; i < nums.size(); ++i) {
            nums[i] = 0;
        }
        }
};

844. 比较含退格的字符串​

class Solution {
    void process(string &st)
    {
        int slow = 0;
        for (int i = 0; i < st.size(); ++i) {
            if ( st[i] != '#') st[slow++] = st[i];
            else
            {
                if (slow > 0) slow--;
            }
        }
        st.resize(slow);
    }
public:
    bool backspaceCompare(string s, string t) {
        process(s);
        process(t);
        return s == t;
    }
};

977. 有序数组的平方​

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int cur = 0;
        int mins = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) {
            nums[i] = nums[i] * nums[i];
            if(nums[i] < mins)
            {
                mins = nums[i];
                cur = i;
            }
        }

        int left = cur - 1, right = cur + 1;
        vector<int> res;
        res.push_back(nums[cur]);
        while(left >= 0 && right < nums.size())
        {
            
            if(nums[left] < nums[right]) 
            {
                cur = left;
                left--;
            }
            else
            {
                cur = right;
                right++;
            }
            res.push_back(nums[cur]);
        }
        while(left >= 0) res.push_back(nums[left--]);
        while(right < nums.size()) res.push_back(nums[right++]);
        
        return res;
    }
};

3. 无重复字符的最长子串​

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() < 2) return s.size();
        unordered_set<char> uset;
        int left = 0 , right = 0, max_len = 0;
        while(right < s.size())
        {
            if(uset.find(s[right]) == uset.end()) uset.insert(s[right]);
            else
            {
                while(s[right] != s[left])
                {
                    uset.erase(s[left++]);
                }
                left++;
            }
            max_len = max(max_len , int(uset.size()));
            right++;
        }
        return max_len;
    }
};

11. 盛最多水的容器​

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0 , right = height.size() - 1 , max_v = 0;
        while(left < right)
        {
            max_v = max(max_v,(right - left) * min(height[left],height[right]));
            if(height[left] < height[right]) left++;
            else right--;
        }
        return max_v;
    }
};

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

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

633. 平方数之和​

class Solution {
public:
    bool judgeSquareSum(int c) {
        if(c < 3) return true;
        long left = 0, right = sqrt(c) + 1;
        while(left <= right)
        {
            if(c == left * left + right * right) return true;
            else if(c > left * left + right * right) left++;
            else right--;
        }
        return false;
    }
};

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

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(),dictionary.end());
        int res = 0;
        string result = "";
        for(string sss:dictionary)   
        {
            int r = 0, l = 0;
            while(r < s.size() && l < sss.size())
            {
                if(s[r] == sss[l]) l++;
                r++;
            }
            if(l == sss.size() && sss.size() > result.size())result = sss;
        }   
        return result;
    }
};

15. 三数之和​

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i = 0 ; i < nums.size() ;i++)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            while(left < right)
            {
                if(nums[i] + nums[left] + nums[right] == 0) 
                {
                    while(nums[left] == nums[left + 1] && left + 1 < right)left++;
                    while(nums[right] == nums[right - 1] && left  < right - 1)right--;
                    res.push_back({nums[i],nums[left++],nums[right--]});
                }
                else if(nums[i] + nums[left] + nums[right] > 0) right--;
                else left++;
            }
        }
        return res;
    }
};

16. 最接近的三数之和​

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res = INT_MAX;
        int result = 0;
        for(int i = 0; i < nums.size();i++)
        {
            if(i > 0 && nums[i] == nums[i - 1])continue;
            int left = i + 1 , right = nums.size() - 1;
            while(left < right)
            {
                int r = nums[i] + nums[left] + nums[right];
                if(res > abs(target - r)) 
                {
                    res = abs(target - r);
                    result = r;
                }
                if(r < target) left++;
                else right--;
            }
        }
        return result;
    }
};

18. 四数之和​

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i = 0 ; i < nums.size() ;i++)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < nums.size();j++)
            {
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.size() - 1;
                while(left < right)
                {
                    if((long long)nums[i] + nums[left] + nums[right] + nums[j] == target) 
                    {
                        while(nums[left] == nums[left + 1] && left + 1 < right)left++;
                        while(nums[right] == nums[right - 1] && left  < right - 1)right--;
                        res.push_back({nums[i],nums[j],nums[left++],nums[right--]});
                    }
                    else if((long long)nums[i] + nums[left] + nums[right] + nums[j] > target) right--;
                    else left++;
                }
            }
        }
        return res;
    }
};

238. 除自身以外数组的乘积​

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        int left=1,right=1;     //left：从左边累乘，right：从右边累乘
        vector<int> res(n,1);
        for(int i=0;i<n;++i)  
        {
            res[i]*=left;       //乘以其左边的乘积
            left*=nums[i];
            res[n-1-i]*=right;  //乘以其右边的乘积
            right*=nums[n-1-i];
        }
        return res;
    }
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面​

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int slow = 0,fast = 0;
        while (fast < nums.size())
        {
            if (nums[fast] % 2 == 1) swap(nums[fast],nums[slow++]);
            fast++;
        }
        return nums;
    }
};

剑指 Offer 57. 和为s的两个数字​

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l = 0 , r = nums.size() - 1;
        while(l < r)
        {
            if(nums[l] + nums[r] == target) break;
            else if(nums[l] + nums[r] < target) l++;
            else r--;
        }
        return {nums[l] , nums[r]};
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列​

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int start = 1, end = 2 ,sum = 3;
        while(start < end)
        {
            if(sum == target)
            {
                vector<int> tmp;
                for(int i = start; i <= end ;i++) tmp.push_back(i);
                res.push_back(tmp);
                sum -= start++;
            }
            else if(sum < target) sum += ++end;
            else sum -= start++;
        }
        return res;
    }
};

1679. K 和数对的最大数目​

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        int left = 0 ,right = nums.size() - 1;
        sort(nums.begin(),nums.end());
        int sums = 0;
        while(left < right)
        {
            if(nums[left] + nums[right] == k) 
            {
                sums++;
                left++;
                right--;
            }
            else if(nums[left] + nums[right] < k) left++;
            else right--;
        }
        return sums;
    }
};

881. 救生艇​

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        //双指针
        int cnt = 0,left = 0, right = people.size() - 1;
        sort(people.begin(),people.end());
        while(left <= right)
        {
            if(people[left] + people[right] <= limit)
            {
                cnt++;
                left++;
                right--;
            }
            else
            {
                cnt++;
                right--;
            }
        }
        return cnt;
    }   
};

滑动窗口​

1004. 最大连续1的个数 III​

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0 , maxsize = 0;
        while(right < nums.size())
        {
            if(nums[right] || k) nums[right++] != 0 ? : k--;
            else nums[left++]  ? : right++;
            maxsize = max(maxsize , right - left);
        }
        return maxsize;
    }
};

424. 替换后的最长重复字符***​

class Solution {
public:
    int characterReplacement(string s, int k) {
        //最长A - Z
        int res = 0;
        for(char ch = 'A' ; ch <= 'Z'; ch++)
        {
            int left = 0, right = 0,lenA = 0,kA = k;
            while(right < s.size())
            {
                if(s[right] == ch|| kA) s[right++] == ch ? : kA--;
                else s[left++] == ch ? : right++;
                lenA = max(lenA,right - left);
            }
            res = max(lenA,res);
        }
        return res;
    }
};

1493. 删掉一个元素以后全为 1 的最长子数组​

（与上一题类似）

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int left = 0 , right = 0,  k = 1 ,max_len = 0;
        while(right < nums.size())
        {
            if(nums[right] || k) nums[right++] ? : k--;
            else nums[left++] ? : right++;
            max_len = max(max_len , right - left - 1);
        }
        return max_len;
    }
};

1156. 单字符重复子串的最大长度​

这几道题使用同样的方法

class Solution {
public:
    int maxRepOpt1(string text) {
        unordered_map<char,int> c_count;
        for(char s : text) c_count[s]++;
        int maxLen = 1;
        for(auto x : c_count)
        {
            int left = 0, right = 0, maxC = 1, k = 1;
            char cur_c = x.first;
            while(right < text.size())
            {
                if(k || text[right] == cur_c) text[right++] == cur_c ? :k--;
                else text[left++] == cur_c ? : right++;
                maxC = max(right - left,maxC);
            }
            maxLen = max({maxLen,min(maxC,x.second)});
        }
        return maxLen;
    }
};

209. 长度最小的子数组​

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(accumulate(nums.begin(),nums.end(),0) < target) return 0;
        int left = 0, right = 0, sums = 0 ,mins = nums.size();
        while(right < nums.size())
        {
            sums += nums[right];
            while(left <= right && sums >= target)
            {
                mins = min(mins , right - left + 1);
                sums -= nums[left++];
            }
            right++;
        }
        return mins;
    }
};

904. 水果成篮​

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
       int left =0,right = 0,ans = 0;
       int ln=fruits[left],rn=fruits[right]; //篮子一号和二号
       while(right < fruits.size())
       {
            if(fruits[right] == rn || fruits[right] == ln){//属于篮子某个种类
                ans = max(ans,right + 1 - left);  //更新结果，每次取一个数就更新一下
                right++;
            }else{//如果遇到第三种，把慢指针移动到快指针前一步，该步的水果种类必然不同于快指针，此时慢指针慢慢回退齐所有的连续同类。（秒啊）
                left = right - 1;  //取到第三种则移动左标到right -1
                ln = fruits[left]; //更新第一个篮子
                while(left >= 1 && fruits[left - 1] == ln) left--;
                rn = fruits[right];
                ans = max(ans,right + 1 - left);
            }
       }
        return ans;
    }
};

LCR 009. 乘积小于 K 的子数组​

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int left = 0, right = 0, count = 0;
        long long psum = 1;
        while(right < nums.size())
        {
            psum *= nums[right];
            while(left <= right && psum >= k) 
            {
                psum /= nums[left++];
            }
            count += right - left + 1;
            right++;
        }
        return count;
    }
};

643. 子数组最大平均数 I​

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum = 0 , max_sum = 0;
        for(int i = 0; i < k; i++) sum += nums[i];
        max_sum = sum;
        for(int i = k ;i < nums.size();i++)
        {
            sum += nums[i] ;
            sum -= nums[i - k] ;
            max_sum = max(max_sum,sum);
        }
        return max_sum / k;
    }
};

1456. 定长子串中元音的最大数目​

class Solution {
public:
    int maxVowels(string s, int k) {
        unordered_set<char> uset({'a','e','i','o','u'});
        function<bool (char)> isy= [&](char x){return uset.find(x) != uset.end();};
        int mins = k , count = 0;
        for(int i = 0; i < k;i++) if(isy(s[i])) count++;
        mins = count;
        for(int i = k; i < s.size();i++)
        {
            count += isy(s[i]) - isy(s[i - k]);
            mins = max(mins , count);
        }
        return mins;
    }
};

1658. 将 x 减到 0 的最小操作数***​

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        //转化为sum - x的最长连续子序列
        x = accumulate(nums.begin(),nums.end(),0) - x;
        int left = 0, right = 0 , sum = 0 , len = -1;
        while(right < nums.size())
        {
            sum += nums[right];
            while(left <= right && sum > x)
            {
                sum -= nums[left];
                left++;
            }
            if(sum == x) len = max(len , right - left + 1);
            right++;
        }
        return len== -1 ? len : nums.size() - len;

    }
};

1423. 可获得的最大点数*​

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        k = cardPoints.size() - k;
        // 转换为k个连续数字的和最小 - 滑动窗口
        int sum = accumulate(cardPoints.begin(),cardPoints.end(),0);
        int left = 0, right = 0, cur = 0, res = sum;
        while(right < k) cur += cardPoints[right++];
        res = min(cur,res);
        while(right < cardPoints.size())
        {
            cur -= cardPoints[left++];
            cur += cardPoints[right++];
            res = min(cur,res);
        }
        return sum - res;
    }
};

30. 串联所有单词的子串​

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = s.size(), m = words.size(), w = words[0].size();
        map<string,int> maps;
        for (string word : words) maps[word]++;
        vector<int> ans;
        //滑动窗口
        for(int cur = 0; cur < w; cur++)
        {
            //从cur 开始，利用滑动窗口进行比较，注意map才能进行直接比较
            map<string,int> temp;
            int i = cur;
            //首先遍历
            while(i < m * w + cur)
            {
                temp[s.substr(i,w)]++;
                i += w;
            }
            
            while(i <= n )
            {
                if(maps == temp) ans.push_back(i - m * w);
                temp[s.substr(i,w)]++;
                string pre = s.substr(i - m * w,w);
                temp[pre]--;
                if(temp[pre] == 0) temp.erase(pre);
                i += w;
            }

        }

        return ans;
    }
};

992. K 个不同整数的子数组​

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        //subarray函数为小于长度k的子数组个数
        function<int(vector<int>&,int)> subarray = [](vector<int>& nums, int k){
            int left = 0, right = 0, cur = 0;
            unordered_map<int,int> umap;
            while(right < nums.size())
            {
                ++umap[nums[right++]];
                while(umap.size() > k)
                {
                    umap[nums[left]]--;
                    if(umap[nums[left]] == 0) umap.erase(nums[left]);
                    left++;
                }
                cur += right - left;
            }
            return cur;
        };
        //等于k的子数组个数 = 小于长度k的子数组个数 - 小于长度k - 1的子数组个数
        return subarray(nums, k) - subarray(nums, k - 1);
    }
};

1234. 替换子串得到平衡字符串​

https://leetcode.cn/problems/replace-the-substring-for-balanced-string/solutions/2108358/tong-xiang-shuang-zhi-zhen-hua-dong-chua-z7tu/

class Solution {
public:
    int balancedString(string s) {
        int n = s.size() , m = n / 4 , cnt['X']{};
        for(char x : s) cnt[x]++;
        if (cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m)
            return 0; // 已经符合要求啦
        int res = n , left = 0;
        for(int right = 0; right < s.size();right++)
        {
            cnt[s[right]]--;
            while(cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m)
            {
                res = min(res,right - left + 1);
                ++cnt[s[left++]];
            }
        }
        return res;
    }
};