左右夹逼
左右指针主要解决 3 类问题
1.二分搜索. 二分搜索是一类经典的问题, 主要是基于某种单调性搜答案, 一个难点在于边界条件的选取, 单独总结在二分查找问题里面
2.用左边和右边两个指针解决的问题, 有些问题需要我们”从两头向中间逼近”, 比如让左右两个指针从两个边缘从外到内去同时扫描
3.用左边和右边两个指针解决的问题, 有些问题需要我们”从中心向两头逼近”, 有时候称为中心扩展算法 expandAroundCenter
167.两数之和II
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。示例 1：输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
分析:
1.有序数组直接维护左右指针扫描
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
vector<int> ans;
if (n == 0)
return ans;
int left = 0;
int right = n - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
ans.push_back(left + 1);
ans.push_back(right + 1);
return ans;
} else if (sum < target) {
++left;
} else if (sum > target) {
--right;
}
}
return ans;
}
};
5.最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。
示例 2：输入：s = “cbbd” 输出：”bb”
分析:
1.以字符串中的某个 i 为中点, 向两边扩展回文字符串找到最长长度, 然后枚举这样的中点找到最长的子串长度
2.扩展有两种形式, 一种是以 i 作为长度数奇串中心, 一种是以 i, 和 i + 1 作为长度偶数中心
3.写 expand() 这个函数, 可以写成兼容奇数和偶数长度两种形式, 用起止点做中心向两边扩散
typedef pair<int, int> pii;
class Solution {
public:
pii expand(int l, int h, string s) {
// aba
// abba
while (l >= 0 && h < s.size() && s[l] == s[h]) {
--l;
++h;
}
return {l+1, h-1};
}
string getStr(pii a, string s) {
return s.substr(a.first, a.second - a.first + 1);
}
string longestPalindrome(string s) {
int len = s.size();
string ans = "";
for (int i = 0; i < len; ++i) {
pii odd = expand(i, i, s);
pii even = expand(i, i+1, s);
string s1 = getStr(odd, s);
string s2 = getStr(even, s);
ans = (ans.size() > s1.size()) ? ans : s1;
ans = (ans.size() > s2.size()) ? ans : s2;
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
