LeetCode分类刷题之双指针（首尾指针）

LeetCode题目太多了，每天随便选题刷没有针对性，效率也很低，今天做了明天就忘了解法。分类刷题效率高，且解题思路形成套路可以更好的举一反三，时间有限的情况下非常推荐分类刷题。

本文及后面的记录文章，所有解法均使用python。

暴力解法是所有思路的起点。

目录

1.两数之和-有序数组（python中数组对应列表，栈也可对应列表）

2.两数的平方和

3.反转字符串中元音字母

4.验证回文串

5.验证回文字符串（加强版）

6.反转字符串

7.盛最多水的容器

---

1.两数之和-有序数组（python中数组对应列表，栈也可对应列表）

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

解题思路：首先题目说给定升序数组，那么肯定有比暴力更好的方法，一般会想到二分法，此题思路类似，用头尾指针来计算两数之和sum，如sum<target，则说明头指针的数值偏小需向右移动，如sum>target则说明尾指针数值偏大需向左移动。两个指针都逐渐向对方移动，也可称为首尾指针。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 特殊情况处理
        if not numbers: return []  

        start, end = 0, len(numbers)-1  #头尾指针

        while start < end:  #保证尾指针在头指针后边
            _sum = numbers[start] + numbers[end]
            if  _sum < target:  #小于目标值，首指针后移
                start += 1
            elif _sum > target: #大于目标值，尾指针前移
                end -= 1
            else:               #等于目标值，返回结果
                return [start + 1, end + 1]
        return []

2.两数的平方和

https://leetcode-cn.com/problems/sum-of-square-numbers/

解题思路：思路与上一题类似，找到两个数的平方和等于target，默认在一个1-n的升序数组中寻找两个数满足条件，问题的关键转化到了n如何确定，观察一下可以发现，n接近target开方的数值，然后就可以采用双指针来确定两个数了。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        assert c >= 0
        start, end = 0, int(sqrt(c)) #设置首尾指针
        while start <= end:
            _sum = start **2 + end **2
            if _sum > c: end -= 1
            elif _sum < c: start += 1
            else: return True
        return False

3.反转字符串中元音字母

https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

解题思路：此题同样是头尾行动，有一个问题就是如何判断字母是不是元音字母，这里可以创建一个元音字母set集合，用in来判断字母是不是集合中的元素。

class Solution:
    def reverseVowels(self, s: str) -> str:
        if len(s)<1: return s
        s = list(s)
        start, end = 0, len(s)-1
        vowels = set('aeiouAEIOU')
        while start < end:
            if s[start] in vowels and s[end] in vowels:
                s[start], s[end] = s[end], s[start]
                start += 1
                end -= 1
            elif s[start] in vowels: end -= 1
            elif s[end] in vowels: start += 1
            else: 
                start +=1
                end -= 1
        return ''.join(s)

4.验证回文串

https://leetcode-cn.com/problems/valid-palindrome/

解题思路：基本原理与之前题目一样，区别在于对字符串的处理，lower() 方法转换字符串中所有大写字符为小写，isalnum() 方法检测字符串是否由字母和数字组成。先用isalnum() 判断是不是字母，再用lower()忽略大小写。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) <= 1: return True
        start, end = 0, len(s)-1
        while start < end:
            if s[start].isalnum() and s[end].isalnum():
                if s[start].lower() == s[end].lower(): 
                    start += 1
                    end -=1
                    continue
                else: return False
            elif s[start].isalnum(): end -= 1
            elif s[end].isalnum() : start += 1
            else:
                start += 1
                end -= 1
        return True

5.验证回文字符串（加强版）

https://leetcode-cn.com/problems/valid-palindrome-ii/

解题思路：与上一题的区别在于可以删除一个字符再来判断是否为回文字符串，并且删除字符有两种情况，一种是删除头指针的一个字符start+1，一种是删除尾指针的一个字符end-1。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if len(s) < 2: return True

        def isPalindrome(s, start, end):
            while start < end:
                if s[start] == s[end]:
                    start += 1
                    end -= 1
                    continue
                else: return False
            return True

        start, end = 0, len(s)-1
        while start < end:
            if s[start] == s[end]:
                start += 1
                end -= 1
                continue
            else: 
                return isPalindrome(s, start+1, end) or isPalindrome(s, start, end-1)
        return True

6.反转字符串

解题思路：这题没啥好说的，首尾指针原地交换

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        start, end = 0, len(s)-1

        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

7.盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

解题思路：题目实际上求的是最大面积，思路可以是先使横轴长度最长，也就是双指针end-start，然后依次移动指针高度最小的来更新面积，同时注意更新面积的写法。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ml = 0 
        start, end = 0, len(height)-1
        while start < end:
            temp = min(height[start], height[end])*(end - start)
            ml = max(temp, ml)
            if height[start] >= height[end]:
                end -= 1
            else:
                start += 1
        return ml

 

本文地址：https://blog.csdn.net/hesongzefairy/article/details/107659722