个人技术分享

• 对撞指针是双指针算法之一。
• 对撞指针从两端向中间迭代数组。一个指针从始端开始，另一个从末端开始。
• 对撞指针的终止条件是两个指针相遇。
• 对撞指针常用于排序数组。

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) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {-1, -1};
    }
};

27. 移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right-1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

125. 验证回文串

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;
    }
};

11. 盛最多水的容器

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度−1变短：

• 若向内 移动短板 ，水槽的短板 min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
• 若向内 移动长板 ，水槽的短板 min(h[i],h[j])不变或变小，因此下个水槽的面积 一定变小 。

因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

算法流程：

• 初始化： 双指针 iii , jjj 分列水槽左右两端；
• 循环收窄： 直至双指针相遇时跳出；
  • 更新面积最大值 res ；
  • 选定两板高度中的短板，向中间收窄一格；
• 返回值： 返回面积最大值 res即可；

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

215. 数组中的第K个最大元素

class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int randIndex = left + rand() % (right - left + 1);
        swap(nums[left], nums[randIndex]);

        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    int findKthLargest(vector<int>& nums, int k) {
        int left = 0, right = nums.size() - 1;
        int targetIndex = nums.size() - k;
        while (left <= right) {
            int mid = partition(nums, left, right);
            if (mid == targetIndex) {
                return nums[mid];
            } else if (mid < targetIndex) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return INT_MIN;
    }
};

• leetcode 对撞指针 解法题目

• 7. 整数反转（easy）
• 9.回文数（easy）
• 27.移除元素（easy）
• 125.验证回文串（easy）
• 167.两数之II-输入有序数组（easy）
• 190.颠倒二进制位（easy）
• 344.反转字符串（easy）
• 345.反转字符串中的元音字母（easy）
• 11.盛水最多的容器（medium）