Skip to content

双指针 Two Pointers

Table of Contents

125. Valid Palindrome

# List Comprehension
def isPalindrome(s: str) -> bool:
    s = [char.lower() for char in s if char.isalnum()]
    return s == s[::-1]


# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


s = "A man, a plan, a canal: Panama"
print(isPalindrome(s))  # True
print(isPalindromeLR(s))  # True

15. 3Sum

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """Two Pointers: O(n^2) time, O(1) space.
        Sort, fix one element, then two-pointer scan for complement.
        """
        n = len(nums)
        if n <= 2:
            return []

        res = []
        nums.sort()

        for k in range(n - 2):
            if k > 0 and nums[k] == nums[k - 1]:
                continue

            i, j = k + 1, n - 1

            while i < j:
                total = nums[k] + nums[i] + nums[j]

                if total > 0:
                    j -= 1
                elif total < 0:
                    i += 1
                else:
                    res.append([nums[k], nums[i], nums[j]])

                    while i < j and nums[i] == nums[i + 1]:
                        i += 1
                    while i < j and nums[j] == nums[j - 1]:
                        j -= 1

                    i += 1
                    j -= 1

        return res


def test_three_sum():
    s = Solution()
    for fn in (s.threeSum,):
        assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
        assert fn([0, 1, 1]) == []
        assert fn([0, 0, 0]) == [[0, 0, 0]]
        assert fn([]) == []

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int left = i + 1, right = n - 1;

        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];

            if (total > 0)
                right--;
            else if (total < 0)
                left++;
            else {
                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--;
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = threeSum(nums);
    for (auto& v : res) {
        for (int i : v) {
            cout << i << " ";
        }
        cout << endl;
    }
    return 0;
}

11. Container With Most Water

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        """Two Pointers: O(n) time, O(1) space.
        Move the shorter side inward to potentially find a taller line.
        """
        left, right = 0, len(height) - 1
        res = 0

        while left < right:
            w = right - left
            h = min(height[left], height[right])
            res = max(res, w * h)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return res

    def maxAreaBF(self, height: List[int]) -> int:
        """Brute Force: O(n^2) time, O(1) space.
        Check every pair of lines.
        """
        res = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                res = max(res, min(height[i], height[j]) * (j - i))
        return res


def test_max_area():
    s = Solution()
    for fn in (s.maxArea, s.maxAreaBF):
        assert fn([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
        assert fn([1, 1]) == 1
        assert fn([4, 3, 2, 1, 4]) == 16
        assert fn([1, 2, 1]) == 2

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int res = 0;

    while (left < right) {
        int h = min(height[left], height[right]);
        int w = right - left;
        res = max(res, h * w);

        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return res;
}

int main() {
    vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << maxArea(height) << endl;  // 49
    return 0;
}