破解面试难题:面试经典150题 之双指针法详解与代码实现

本文主要是介绍破解面试难题:面试经典150题 之双指针法详解与代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

面试经典 150 题 - 学习计划 - 力扣（LeetCode）全球极客挚爱的技术成长平台https://leetcode.cn/studyplan/top-interview-150/

125. 验证回文串

125. 验证回文串

 STL容器

思路：

1. 遍历输入的字符串，将其中的字母字符转换为小写，并保留数字字符，放入另一个字符串 s1 中。
2. 将 s1 复制给另一个字符串 s2。
3. 将 s1 反转，得到逆序字符串。
4. 比较原字符串 s1 和逆序字符串 s2 是否相等，若相等则返回 true，否则返回 false。

class Solution {
public:bool isPalindrome(string s) {string s1;for(auto &c : s) {if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { s1 += tolower(c);} else if(c >= '0' && c <= '9'){ s1 += c;}}string s2;s2=s1;reverse(s1.begin(),s1.end());if(s1 == s2)return true;elsereturn false;}
};

双指针

思路：

1. 遍历输入的字符串，将其中的字母字符转换为小写，并保留数字字符，放入另一个字符串 s1 中。
2. 初始化两个指针 left 和 right 分别指向 s1 的开头和结尾。
3. 使用双指针方法，依次比较 left 和 right 指向的字符，如果不相等，则返回 false；如果相等，则继续向中间移动指针。
4. 如果遍历完成后都没有出现不相等的情况，说明该字符串是回文字符串，返回 true。

class Solution {
public:bool isPalindrome(string s) {string s1;for(auto &c : s) {if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { s1 += tolower(c);} else if(c >= '0' && c <= '9'){ s1 += c;}}int left = 0;int right = s1.length()-1;while(left<right){if(s1[left] != s1[right])return false;++left;--right;}return true;}
};

 392. 判断子序列

 392. 判断子序列

思路：

1. 初始化两个指针 i 和 j 分别指向字符串 s 和 t 的起始位置。
2. 遍历字符串 t，当字符 t[j] 等于字符 s[i] 时，将两个指针都向后移动一位。
3. 如果最终 i 移动到了 s 的末尾，说明 s 是 t 的子序列，返回 true；否则，返回 false。

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++;}   if(i==s.size())return true;return false;}
};

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

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

思路：

1. 使用双指针，一个指针 i 指向数组的起始位置，另一个指针 j 指向数组的末尾位置。
2. 在每次迭代中，计算指针 i 和指针 j 指向的元素之和 numbers[i] + numbers[j]。
3. 如果和大于目标值 target，则将指针 j 向左移动一位，以减小和的值。
4. 如果和小于目标值 target，则将指针 i 向右移动一位，以增加和的值。
5. 如果和等于目标值 target，则找到了符合条件的数对，将它们的索引加1并加入结果数组中，然后退出循环。(因为只有一对正确的答案)
6. 最终返回结果数组。

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

 11. 盛最多水的容器

11. 盛最多水的容器

思路：

1. 使用双指针，一个指针 i 指向数组的起始位置，另一个指针 j 指向数组的末尾位置。
2. 在每次迭代中，计算当前容器的容量，即 (j - i) * min(height[i], height[j])。
3. 每次计算完容量后，更新记录的最大容量 mx，将当前容量与 mx 比较取较大值。
4. 如果 height[i] < height[j]，则移动指针 i 向右一位；否则移动指针 j 向左一位。
5. 重复步骤 2 到 4，直到指针 i 和 j 相遇为止。
6. 返回记录的最大容量 mx。

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

15. 三数之和

15. 三数之和

思路：

1. 首先对数组进行排序，这样可以方便地使用双指针来遍历数组。
2. 然后使用三个指针 i, left, right 分别指向排序后数组中的每个元素、当前元素的下一个元素和数组末尾元素。
3. 在每一轮循环中，固定指针 i，并初始化 left = i + 1 和 right = n - 1，其中 n 是数组的长度。
4. 在 left 和 right 指针确定的范围内，使用双指针技巧来寻找和为 0 的两个数。
5. 如果找到了满足条件的三元组，则将其加入结果集中，并且需要注意去重。
6. 继续遍历数组，直到 i 指针到达倒数第三个元素为止。

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

这篇关于破解面试难题:面试经典150题 之双指针法详解与代码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---