面试经典 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;}
};