双指针

• 1.数对和

• 2.平方数之和

• 3.颜色分类

• 4.仅仅反转字母

• 5.验证回文字符串II

• 6.最短无序连续子数组

• 7.分发饼干

1.LeetCode面试题 16.24.数对和

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 1:

输入: nums = [5,6,5], target = 11
输出: [[5,6]]
示例 2:

输入: nums = [5,6,5,6], target = 11
输出: [[5,6],[5,6]]

class Solution:
    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res,n=[],len(nums)

        i,j=0,n-1
        while i<j:
            if nums[i]+nums[j]<target:
                i+=1
            elif nums[i]+nums[j]>target:
                j-=1
            else:
                res.append([nums[i],nums[j]])
                i+=1
                j-=1
        return res

2.LeetCode 633.平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        import math
        x=math.floor(math.sqrt(c))
        i,j=0,x
        while i<=j:
            if i**2+j**2<c:
                i+=1
            elif i**2+j**2>c:
                j-=1
            else:
                return True
        return False

3.LeetCode 75.颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i,j,k=0,0,len(nums)-1       #三指针，j前面的全0即红色，j~k全1即白色，k之后的全2即蓝色
        while j<=k:
            if nums[j]==0:          #j遇到红色，与i位置交换
                nums[j]=nums[i]
                nums[i]=0
                i+=1
                j+=1                #j交换来的i一定是红色的，所以i和j分别加1
            elif nums[j]==1:        #j遇到白色，直接加1
                j+=1
            else:
                nums[j]=nums[k]     #j遇到蓝色，与k位置交换
                nums[k]=2
                k-=1

4.LeetCode 917.仅仅反转字母

给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例 ：

输入："Test1ng-Leet=code-Q!"

输出："Qedo1ct-eeLg=ntse-T!"

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        j=len(S)-1
        n,res=len(S),[]

        for i in range(n):
            if S[i].isalpha():          #i是字母，从j开始往前第一个是字母的字符，添入列表
                while not S[j].isalpha():
                    j-=1
                res.append(S[j])
                j-=1
            else:                       #i不是字母，将其本身添入列表
                res.append(S[i])
        return ‘‘.join(res)

除了双指针的方法，提供另一种栈的思路

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        lst,res=[],[]                     #将所有字母字符存入lst
        for k in S:
            if k.isalpha():
                lst.append(k)
        
        for x in S:
            if x.isalpha():               #x是字符，将列表中的最后一位出列，存入res
                res.append(lst.pop())
            else:                         #x不是字符，将其本身存入res          
                res.append(x)
        return ‘‘.join(res)

5.LeetCode 680.验证回文字符串II

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 :

输入: "abca"
输出: True
解释: 你可以删除c字符。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i,j=0,len(s)-1
        while i<j:
            if s[i]!=s[j]:          
                s1=s[:i]+s[i+1:]        #舍弃第i位
                s2=s[:j]+s[j+1:]        #舍弃第j位
                return s1==s1[::-1] or s2==s2[::-1]
            i+=1
            j-=1
        return True

6.LeetCode 581.最短无序连续子数组

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        tmp=sorted(nums)            
        i,j=0,len(nums)-1
        while i<j:
            if tmp[i]==nums[i]:
                i+=1
            if tmp[j]==nums[j]:
                j-=1
            if tmp[i]!=nums[i] and tmp[j]!=nums[j]:
                return j-i+1
        return 0

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        
        peo,bis=len(g),len(s)
        i,j,count=0,0,0
        while i<peo and j<bis:
            if g[i]<=s[j]:
                count+=1
                i+=1
                j+=1
            else:
                j+=1
        return count