【LeetCode】C++：数组类算法-双索引技巧-对撞指针
目录
167. 两数之和 II - 输入有序数组
125.验证回文串
345.反转字符串中的元音字母
11.盛最多水的容器
209.长度最小的数组
167. 两数之和 II - 输入有序数组
给你一个下标从1开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等目标 target的两个数。如果设这两个数分别是numbers[index1]和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你不可以重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
思考：
已知：非递减序列==从大到小序列
要求：从序列找出2个数之和==目标值，返回的是下标序列，不重复使用相同元素
理念：达到要求就返回！
策略1：遍历，当前元素和后面元素遍历循环，满足即输出。
但是没有用到序列特性，非递减！---暴力解法
策略2：对撞指针，指针 i 和 j 分别指向数组的第一个元素和最后一个元素，然后指针 i 不断向前， 指针 j 不断递减，直到 i = j？--对撞指针法
情况：
- 两元素之和=目标值，return
- 两元素之和<目标值，begin+1
- 两元素之和>目标值，end-1
class Solution {
public:vector twoSum(vector& numbers, int target) {int n=numbers.size();int end=n-1;int begin=0;while(begin 125.验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
- 字母和数字都属于字母数字字符。
- 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
思考：
1.大写字符转换为小写字符 内置函数？tolower()
2.移除所有非字母数字字符【字母+数字=字母数字字符】判断移除？isalnum()
3.正序==倒序，对称相等，遍历？对撞指针？
isalnum():检查所传的字符是否是字母和数字。
tolower():给定的字母转换为小写字母。
for(char c:s)==for( int i = 0; i < s.length(); i++) { s[i].... }
class Solution {
public:bool isPalindrome(string s) {string sgood;for (char ch: s) {if (isalnum(ch)) {sgood += tolower(ch);}}int n = sgood.size();int left = 0, right = n - 1;while (left < right) {if (sgood[left] != sgood[right]) {return false;}++left;--right;}return true;}
};345.反转字符串中的元音字母
给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。
思考：
1.反换元音字母，首先找到元音字母，头尾对应交换？
2.支持大小写
isVowel！
auto isVowel = [vowels = "aeiouAEIOU"s](char ch)
class Solution {
public:string reverseVowels(string s) {auto isVowel = [vowels = "aeiouAEIOU"s](char ch) {return vowels.find(ch) != string::npos;};int n = s.size();int i = 0, j = n - 1;while (i < j) {while (i < n && !isVowel(s[i])) {++i;}while (j > 0 && !isVowel(s[j])) {--j;}if (i < j) {swap(s[i], s[j]);++i;--j;}}return s;}
};11.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
- 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
- 返回容器可以储存的最大水量。
- 说明：你不能倾斜容器。
思考：
1.就是找寻最大的两个元素的最小值？同时保证元素索引相聚最大？
2.容量即面积？
【官方详解】
class Solution {
public:int maxArea(vector& height) {int l = 0, r = height.size() - 1;int ans = 0;while (l < r) {int area = min(height[l], height[r]) * (r - l);ans = max(ans, area);if (height[l] <= height[r]) {++l;}else {--r;}}return ans;}
}; 209.长度最小的数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
【官方解读】【多方法】【进阶学习】
class Solution {
public:int minSubArrayLen(int s, vector& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;int start = 0, end = 0;int sum = 0;while (end < n) {sum += nums[end];while (sum >= s) {ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans == INT_MAX ? 0 : ans;}
};