算法题 - 双指针

125. 验证回文串

LeetCode_link

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

示例 2：
输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。

示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

提示：
1 <= s.length <= 2 * 105
s 仅由可打印的 ASCII 字符组成

节省空间版

class Solution {
public:
    bool isPalindrome(string s) {
        //去掉其他东西
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= 'A' && s[i] <= 'Z'){
                s[i] = 'a' + s[i] - 'A';
            }else if(!(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= '0' && s[i] <= '9')){
                s.erase(i, 1);
                i --;
            }
        }
        int i = 0, j = s.size() - 1;
        while(i <= j){
            if(s[i] == s[j]){
                i++;j--;
            }else{
                return false;
            }
        }
        return true;
    }
};

392. 判断子序列

LeetCode_link

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false

提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        if(n == 0)  return true; // 空串是任意字符串的子串
        if(m == 0) return false;
        int i = 0, j = 0;
        while(i < n && j < m){
            if(s[i] == t[j]){
                cout << "s[i]: " << s[i] << " t[j]: "  << t[j] << endl;
                i ++;
            }
            j ++;
        }
        if(i < n && j >= m) return false;
        return true;

    }
};

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

LeetCode_link

给你一个下标从 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] 。

提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按非递减顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

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

    }
};

11. 盛最多的水

LeetCode_link

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：
在这里插入图片描述

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：
输入：height = [1,1]
输出：1

提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

思路：将短板向内变化，寻找能让面积变大的可能性

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

15. 三数之和

LeetCode_link

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

思路：固定一个数，让另外两个数双指针移动。注意可能存在重复的数字。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> rec;
        for(int k = 0; k < n; k++){ //k是固定的数
            if(k > 0 && nums[k] == nums[k-1])   continue;  //去掉重复项
            int i = k + 1, j = n - 1;
            while(i < j){
                if(nums[i] + nums[j] + nums[k] < 0){
                    i++;
                }else if(nums[i] + nums[j] + nums[k] > 0){
                    j --;
                }else{
                    rec.push_back({nums[i], nums[j], nums[k]});
                    while (i+1 < n && nums[i] == nums[++i]);  //去掉重复项
                    while (j-1 > 0 && nums[j] == nums[--j]);
                }
            }
        }
        return rec;
    }
};