刷题 双指针 滑动窗口

面试经典 150 题 - 双指针

⭐️125. 验证回文串

学会内部字母处理函数的使用

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left <= right) {
            // 处理左边字符
            if (!isalnum(s[left])) {
                ++left;
                continue;
            }
            // 处理右边字符
            if (!isalnum(s[right])) {
                --right;
                continue;
            }
            // 忽略大小写后比较字符
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

392. 判断子序列 - 贪心

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

167. 两数之和 II - 输入有序数组 - 双向双指针

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

⭐️11. 盛最多水的容器

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0, n = height.size();
        for (int l = 0, r = n - 1; l < r;) {
            ans = max(ans, min(height[l], height[r]) * (r - l));
            // 移动较长边：面积一定缩小
            // 移动较短边: 面积有可能变大
            if (height[l] < height[r]) {
                ++l; 
            } else {
                --r;
            }
        }
        return ans; 
    }
};

15. 三数之和 - 双向双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            while (i > 0 && i < n - 2 && nums[i] == nums[i - 1]) {
                ++i;
            }
            if (nums[i] > 0) {
                break;
            }
            for (int j = i + 1, k = n - 1; j < k;) {
                if (nums[k] < 0) {
                    break;
                }
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) {
                    ++j;
                } else if (sum > 0) {
                    --k;
                } else {
                    result.push_back({nums[i], nums[j], nums[k]});
                    ++j;
                    --k;
                    while (j < k && nums[j] == nums[j - 1]) {
                        ++j;
                    }
                    // while (k > j && nums[k] == nums[k - 1]) {
                    //     --k;
                    // }
                }
            }
        }
        return result;
    }
};

原文地址：https://blog.csdn.net/weixin_44797288/article/details/142744209

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！