本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站，刷题按Tag分类。本系列题解汇总如下 (持续更新…)：

本文主要是双指针相关题目题解总结。

[TOC]

双指针

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

11. 盛最多水的容器

题目描述

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

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

示例:

1 2	输入: [1,8,6,2,5,4,8,3,7] 输出: 49

解题思路

双指针法，一个从前往后，一个从后往前，计算两个挡板之间的面积，然后向中间移动，那个挡板比较矮，就舍弃这个挡板。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height <= 1:
            return False
        
        res = 0
        left, right = 0, len(height)-1
        while left < right:
            temp = (right-left)*min(height[left], height[right])
            if temp > res:
                res = temp
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return res

15. 三数之和

题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

先对数组进行排序，然后遍历数组，对每个位置都从它的后一个元素到末尾取两个元素加和，如果为0就添加到结果数组中。需要跳过相同的数字。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) <= 2:
            return []
        
        nums.sort()
        
        res = []
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while right > left and nums[right] == nums[right+1]:
                        right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        
        return res

16. 最接近的三数之和

题目描述

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
3

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if len(nums) <= 2:
            return 0
        
        nums.sort()
        res = float('inf')
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left, right = i+1, len(nums)-1
            while left < right:
                temp = nums[i]+nums[left]+nums[right]
                if abs(temp-target) < abs(res-target):
                    res = temp
                if temp == target:
                    return target
                elif temp < target:
                    left += 1
                else:
                    right -= 1
        
        return res

26. 删除排序数组中的重复项

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

双指针。第一个指向当前不重复的位置len，另一个不断向后遍历遇到不重复的就写到len位置。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) <= 1:
            return len(nums)
        
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        
        return i + 1

27. 移除元素

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        
        return i

28. 实现strStr()

题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

1 2	输入: haystack = "hello", needle = "ll" 输出: 2

示例 2:

1 2	输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解题思路

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        
        if len(needle) == 0:
            return 0
        if len(haystack) == 0 or len(haystack) < len(needle):
            return -1
        
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        
        return -1

75. 颜色分类

题目描述

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

注意:

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

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路

设置两个头尾指针，头指针p0指向的位置是0该放置的位置，尾指针p2指向的位置是2该放置的位置。
i用来遍历整个数组，碰到0把它和p0指向的数交换，碰到2把它和p2指向的数交换，碰到1继续向后遍历。
有点类似快速排序的分割数组这一步。

class Solution:
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        p0, p2 = 0, len(nums) -1 
        i = 0
        while i <= p2:
            if nums[i] == 0:
                nums[i],nums[p0] = nums[p0], nums[i]
                i += 1
                p0 += 1
            elif nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            else:
                i += 1

80. 删除排序数组中的重复项 II

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题思路

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) <= 1:
            return len(nums)
        
        left = 0
        for n in nums:
            if left < 2 or n > nums[left-2]:
                nums[left] = n
                left += 1
        
        return left

88. 合并两个有序数组

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出:
[1,2,2,3,5,6]

解题思路

从尾向前遍历，设置两个指针p1和p2遍历数组，p1，p2分别从m-1和n-1开始向前遍历；
每一次遍历将大的元素放到nums1后面（最后一位为m-n+1），并向前移动一步，直到一个数组先遍历完成；
若nums1首先遍历完成，则需要将nums2剩下的元素放到nums1的前面。

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        if len(nums1)< m+n:
            return False
        p1,p2 = m-1,n-1
        point = m+n-1
        while p1>= 0 and p2 >= 0:
            if nums1[p1]<nums2[p2]:
                nums1[point] = nums2[p2]
                p2 -= 1
            else:
                nums1[point] = nums1[p1]
                p1 -= 1
            point -= 1
        if p2 >= 0:
            nums1[:p2+1] = nums2[:p2+1]

if __name__ == '__main__':
    result = Solution().merge([1,2,3,0,0,0],3,[2,5,6],3)
    print(result)

125. 验证回文串

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：

本题中，我们将空字符串定义为有效的回文串。
示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
示例 2:

输入: “race a car”
输出: false

解题思路

新建一个字符串，将所有数字字母保存；使用双指针，left从头向后遍历，right从后向前遍历，判断left和right指向的元素是否相等。

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == '':
            return True
        new = ''
        for x in s:
            if x.isalnum():
                new += x.lower()
        left, right = 0, len(new)-1
        while left <= right:
            if new[left] != new[right]:
                return False
            left += 1
            right -= 1
        return True
    
if __name__ == '__main__':
    result = Solution().isPalindrome("A man, a plan, a canal: Panama")
    print(result)

二刷

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) <= 1:
            return True
        
        s = s.lower()
        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] != s[right]:
                return False
            left += 1
            right -= 1
        
        return True

141. 环形链表

题目描述

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

解题思路

使用双指针，一个一次走两步，另一个一次走一步，若有环，则必然相遇。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

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

题目描述

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明：

返回的下标值（index1 和 index2）不是从零开始，
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例：

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2。

解题思路

使用两个指针left和right，left指向数组第一个元素并从头向后遍历，right指向数组最后一个元素并从尾向前遍历：

如果两个指针指向元素之和numbers[left]+numbers[right] == target, 则返回 [left+1,right+1]，结束；
如果两个指针指向元素之和numbers[left]+numbers[right] > target，则right -= 1；
如果两个指针指向元素之和numbers[left]+numbers[right] < target，则left += 1。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(numbers) < 2:
            return []
        left, right = 0, len(numbers)-1
        while left < right:
            if numbers[left]+numbers[right] == target:
                return [left+1, right+1]
            elif numbers[left]+numbers[right] > target:
                right -= 1
            else:
                left += 1
        return []

if __name__ == '__main__':
    result = Solution().twoSum([2,7,11,15], 9)
    print(result)

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

题目描述

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

1
2
3

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        if len(numbers) <= 1:
            return []
        
        left, right = 0, len(numbers)-1
        while left < right:
            if numbers[left]+numbers[right] == target:
                return [left+1, right+1]
            elif numbers[left]+numbers[right] > target:
                right -= 1
            else:
                left += 1
        
        return []

209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

1
2
3

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        left, right = 0, 0
        
        res = float('inf')
        while right < len(nums) and left <= right:
            if sum(nums[left:right+1]) >= s:
                res = min(res, right-left+1)
                left += 1
            else:
                right += 1
        
        return res if res != float('inf') else 0

345. 反转字符串中的元音字母

题目描述

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

输入: “hello”
输出: “holle”
示例 2:

输入: “Leetcode”
输出: “leotcede”
说明:

元音字母不包含字母”y”。

解题思路

元音字母有五个：aAeEIioOuU。使用双指针，left从头向后遍历，right从后向前遍历，分别找到元音字母时时进行一次交换。

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        vowels = 'aAeEiIoOuU'
        s = list(s)
        left, right = 0, len(s)-1
        while left < right:
            while left < right and s[left] not in vowels:
                left += 1
            while right  > left and s[right] not in vowels:
                right -= 1
            if left < right:
                s[left],s[right] = s[right], s[left]
            left += 1
            right -= 1
        return ''.join(s)

if __name__ == '__main__':
    result = Solution().reverseVowels("Leetcode")
    print(result)

524. 通过删除字母匹配到字典里最长单词

题目描述

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
输出:
“apple”
示例 2:

输入:
s = “abpcplea”, d = [“a”,”b”,”c”]
输出:
“a”
说明:

所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

解题思路

先把d中元素排序，以长度为主，字典序为辅；
然后遍历d中字符串，依此判断是否满足条件，满足条件则返回；
因为经过了排序，第一个满足条件的可以保证返回长度最长且字典顺序最小的字符串。

class Solution(object):
    def findLongestWord(self, s, d):
        """
        :type s: str
        :type d: List[str]
        :rtype: str
        """
        if len(d) == 0 or len(s) == 0:
            return ''
        d = sorted(d, key=lambda x: (-len(x), x))
        res = ''
        for x in d:
            if self.judge(s,x):
                return x
        return ''

    def judge(self,s,x):
        if len(s) < len(x):
            return False
        p1,p2 = 0, 0
        while p1 < len(s) and p2 < len(x):
            if s[p1] == x[p2]:
                p1 += 1
                p2 += 1
            else:
                p1 += 1
        if p2 == len(x):
            return True
        return False

if __name__ == '__main__':
    result = Solution().findLongestWord("abpcplea", ["ale","apple","monkey","plea"])
    print(result)

633. 平方数之和

题目描述

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

示例1：

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

输入: 3
输出: False

解题思路

假设\(a=0\)，则 \(b=\sqrt{c}\)，则最大整数为 \(\sqrt{c}\)，设置两个指针，left指向0并向前遍历，right指向\(\sqrt{c}\)并向后遍历：

如果 left*left+right*right = c，返回True,结束；
如果 left*left+right*right > c， right -= 1；
如果 left*left+right*right < c， left += 1；

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        if c < 0:
            return False
        left, right = 0, int(pow(c,1.0/2))
        while left <= right:
            if left*left+right*right == c:
                return True
            elif left*left+right*right > c:
                right -= 1
            else:
                left += 1
        return False

if __name__ == '__main__':
    result = Solution().judgeSquareSum(6)
    print(result)

680. 验证回文字符串 Ⅱ

题目描述

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

示例 1:

输入: “aba”
输出: True
示例 2:

输入: “abca”
输出: True
解释: 你可以删除c字符。
注意：

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

解题思路

使用双指针，找到第一个不相等的位置后，去除left或着right后判断是否成为回文。

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        left, right = 0, len(s)-1
        while left <= right:
            if s[left] != s[right]:
                return self.isPalindrome(s[:left]+s[left+1:]) or self.isPalindrome(s[:right]+s[right+1:])
            left += 1
            right -= 1
        return True
    def isPalindrome(self,s):
        left ,right = 0, len(s)-1
        while left <= right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

if __name__ == '__main__':
    result = Solution().validPalindrome("aba")
    print(result)