双指针

1. 两数之和

难度简单7860收藏分享切换为英文关注反馈

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_len = len(nums)
        nums_copy = list()

        for index in range(nums_len):
            nums_copy.append([nums[index],index])
  
        nums_copy.sort(key=lambda x: x[0])
        front_point, back_point =  0, nums_len - 1

        while front_point < back_point:
            if nums_copy[front_point][0] + nums_copy[back_point][0] > target:
                back_point -= 1
            elif nums_copy[front_point][0] + nums_copy[back_point][0] < target:
                front_point += 1
            else:
                return [nums_copy[front_point][1], nums_copy[back_point][1]]
        return []

11. 盛最多水的容器

难度中等1204收藏分享切换为英文关注反馈

给你 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,8,6,2,5,4,8,3,7]
输出：49

class Solution:
    def maxArea(self, height: List[int]) -> int:
        front_point, back_point = 0, len(height) - 1
        max_area = 0
        
        while back_point > front_point:
            min_height = min(height[front_point], height[back_point])
            temp_max_area = min_height *(back_point - front_point)

            if temp_max_area > max_area:
                max_area = temp_max_area
            if height[front_point] == min_height:
                front_point += 1
            else:
                back_point -= 1

        return max_area

15. 三数之和

难度中等1904收藏分享切换为英文关注反馈

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

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

示例：

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

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

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        
        nums_size = len(nums)
        if nums_size <= 1:
            return []
        
        nums.sort()
        
        res = []
        
        for index in range(nums_size-2):
            if nums[index] > 0:
                break
            if index > 0 and nums[index] == nums[index - 1]:
                continue
            front_point, back_point = index + 1, nums_size - 1
            
            while front_point < back_point:
                sum_3_nums = nums[index] + nums[front_point] + nums[back_point]
                if sum_3_nums < 0:
                    front_point += 1
                    while front_point  < back_point and nums[front_point - 1] == nums[front_point]:
                        front_point += 1
                elif sum_3_nums > 0:
                    back_point -= 1 
                    while front_point < back_point and nums[back_point + 1] == nums[back_point]:
                        back_point -= 1
                else:
                    temp = [nums[index], nums[front_point], nums[back_point]]
                    res.append(temp[:])
                    front_point += 1
                    back_point -= 1 
                    while front_point  < back_point and nums[front_point - 1] == nums[front_point]:
                        front_point += 1
                    while front_point < back_point and nums[back_point + 1] == nums[back_point]:
                        back_point -= 1            
            
        return res

16. 最接近的三数之和

难度中等381收藏分享切换为英文关注反馈

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

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

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

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if not nums:
            return None
        nums_size = len(nums)
        
        if nums_size <= 1:
            return None
        
        nums.sort()
        min_difference = float("inf")
        
        for index in range(nums_size - 2):
            
            #去重
            if index > 0 and nums[index - 1] == nums[index]:
                continue
                
            front_point, back_point = index + 1, nums_size - 1
        
            while front_point < back_point:
                sums_3_nums = nums[index] + nums[front_point] + nums[back_point]
                difference =  sums_3_nums - target
                if abs(difference) < abs(min_difference):
                    min_difference = difference
                    
                if difference < 0:
                    front_point += 1
                    #去重
                    while front_point < back_point and nums[front_point] == nums[front_point - 1]:
                        front_point += 1
                elif difference > 0:
                    back_point -= 1
                    #去重
                    while front_point < back_point and nums[back_point] == nums[back_point + 1]:
                        back_point -= 1                    
                else:
                    return target
                    
        return target + min_difference

18. 四数之和

难度中等408收藏分享切换为英文关注反馈

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

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

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums:
            return []
        
        nums_size = len(nums)
        if nums_size <= 3:
            return []
        
        nums.sort()
        print(nums)
        res = []
        
        for index in range(nums_size - 3):
            
            if nums[index] > target //4:
                break
            
            if index > 0 and nums[index] == nums[index - 1]:
                continue
                
            for j_index in range(index + 1, nums_size-2):
                if j_index > index + 1 and nums[j_index] == nums[j_index - 1]:
                    continue
                
                front_point, back_point = j_index + 1, nums_size - 1
            
                while front_point < back_point:
                    sum_4_nums = nums[index] + nums[j_index] + nums[front_point] + nums[back_point]
                    diffirence = sum_4_nums - target    
                    if diffirence < 0:
                        front_point += 1
                        while front_point  < back_point and nums[front_point - 1] == nums[front_point]:
                            front_point += 1
                    elif diffirence > 0:
                        back_point -= 1 
                        while front_point < back_point and nums[back_point + 1] == nums[back_point]:
                            back_point -= 1
                    else:
                        temp = [nums[index], nums[j_index], nums[front_point], nums[back_point]]
                        res.append(temp[:])
                        front_point += 1
                        back_point -= 1 
                        while front_point  < back_point and nums[front_point - 1] == nums[front_point]:
                            front_point += 1
                        while front_point < back_point and nums[back_point + 1] == nums[back_point]:
                            back_point -= 1    
                                    
        return res

19. 删除链表的倒数第N个节点

难度中等725收藏分享切换为英文关注反馈

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        slow_point, fast_point = head, head
        
        for _ in range(n):
            fast_point = fast_point.next
                
        if not fast_point:
            return head.next
        
        while fast_point.next:
            slow_point = slow_point.next
            fast_point = fast_point.next
            
        slow_point.next = slow_point.next.next
        
        return head

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

难度简单1358收藏分享切换为英文关注反馈

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

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 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。

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

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        nums_size = len(nums)
        if nums_size == 1:
            return 1
        
        slow_point, fast_point = 1, 1
        
        for fast_point in range(1, nums_size):
            if nums[fast_point] != nums[fast_point - 1]:
                nums[slow_point] = nums[fast_point]
                slow_point += 1
            else:
                continue
                
        return slow_point

27. 移除元素

难度简单499收藏分享切换为英文关注反馈

给你一个数组 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。

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

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

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if not nums:
            return 0
        
        slow_point, fast_point = 0, 0
        
        for fast_point in range(len(nums)):
            if nums[fast_point] != val:
                nums[slow_point] = nums[fast_point]
                slow_point += 1
        
        return slow_point

28. 实现 strStr()

难度简单383收藏分享切换为英文关注反馈

实现 strStr() 函数。

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

示例 1:

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

示例 2:

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

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        haystack_size, needle_size = len(haystack), len(needle)
        slow_point = 0
        
        while slow_point <= haystack_size - needle_size:
            if haystack[slow_point: slow_point + needle_size] == needle:
                return slow_point
            slow_point += 1
            
        return -1

61. 旋转链表

难度中等217收藏分享切换为英文关注反馈

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

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

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        if not head.next:
            return head
        fast_point, slow_point = head, head
        length = self.lengthList(head)
        
        #k大于等于链表长度        
        if k >= length:
            for _ in range(k%length):
                front_point, back_point = head, head.next
                while back_point.next:
                    back_point = back_point.next
                    front_point = front_point.next
                back_point.next = head
                front_point.next = None
                head = back_point
            return head

        #k小于链表长度 
        for _ in range(k):
            if fast_point:
                fast_point = fast_point.next
            else:
                break  

        while fast_point.next:
            slow_point = slow_point.next
            fast_point = fast_point.next
        fast_point.next = head
        head = slow_point.next
        slow_point.next = None

        return head

    def lengthList(self, head: ListNode) -> int:
        temp = head
        length = 0
        while temp:
            length += 1
            temp = temp.next

        return length

 

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

难度中等195收藏分享切换为英文关注反馈

 

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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 。

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

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        nums_size = len(nums)
        if nums_size == 1:
            return 1
            
        slow_point, fast_point = 0, 0
        
        for fast_point in range(0, nums_size):
            if fast_point == 0 or (fast_point > 0 and nums[fast_point] != nums[fast_point - 1]):
                temp_num_time = 1
                nums[slow_point] = nums[fast_point]
                slow_point += 1
            elif temp_num_time == 1:
                temp_num_time += 1
                nums[slow_point] = nums[fast_point]
                slow_point += 1
            else:
                continue

        return slow_point

86. 分隔链表

难度中等171收藏分享切换为英文关注反馈

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

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

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head:
            return None
        smallerNode = ListNode(0)
        biggerNode = ListNode(x)
        
        smaller_pointer, bigger_pointer = smallerNode, biggerNode
        pointer = head
        while pointer:
            if pointer.val < x:
                smaller_pointer.next = pointer
                smaller_pointer = smaller_pointer.next
                pointer = pointer.next
                smaller_pointer.next = None
            else:
                bigger_pointer.next = pointer
                bigger_pointer = bigger_pointer.next
                pointer = pointer.next
                bigger_pointer.next = None
            
        smaller_pointer.next = biggerNode.next

        return smallerNode.next

88. 合并两个有序数组

难度简单446收藏分享切换为英文关注反馈

给你两个有序整数数组 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]

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m + n == 0:
            return 
        
        slow_pointer = m + n - 1
        nums1_pointer = m - 1
        nums2_pointer = n - 1
        
        while nums1_pointer >= 0 and nums2_pointer >= 0:
            if nums1[nums1_pointer] >= nums2[nums2_pointer]:
                nums1[slow_pointer] = nums1[nums1_pointer]
                nums1_pointer = nums1_pointer - 1
                slow_pointer = slow_pointer - 1
            else:
                nums1[slow_pointer] = nums2[nums2_pointer]
                nums2_pointer = nums2_pointer - 1
                slow_pointer = slow_pointer - 1
                
        while nums1_pointer >= 0:
            nums1[slow_pointer] = nums1[nums1_pointer]
            nums1_pointer = nums1_pointer - 1
            slow_pointer = slow_pointer - 1  
            
        while nums2_pointer >= 0:
            nums1[slow_pointer] = nums2[nums2_pointer]
            nums2_pointer = nums2_pointer - 1
            slow_pointer = slow_pointer - 1                
                
        return 

125. 验证回文串

难度简单166收藏分享切换为英文关注反馈

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

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

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

141. 环形链表

难度简单523收藏分享切换为英文关注反馈

给定一个链表，判断链表中是否有环。

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

示例 1：

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

示例 2：

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

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        
        slow_pointer, fast_pointer = head, head
        
        while fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next
            if fast_pointer == slow_pointer:
                return True
            elif not fast_pointer:
                break
            
        return False

142. 环形链表 II

难度中等393收藏分享切换为英文关注反馈

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

说明：不允许修改给定的链表。

示例 1：

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

示例 2：

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

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        slow_pointer, fast_pointer = head, head
        
        while fast_pointer.next:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next
            if fast_pointer == slow_pointer:
                fast_pointer = head
                while fast_pointer != slow_pointer:
                    fast_pointer = fast_pointer.next
                    slow_pointer = slow_pointer.next
                return slow_pointer
            elif not fast_pointer:   
                break    
                
        return None     

 NC128 容器盛水问题

链接：https://www.nowcoder.com/questionTerminal/f92929ec6e5642a690e7c197b0c40e38?orderByHotValue=1&mutiTagIds=1579&page=1&onlyReference=false
来源：牛客网
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。 

具体请参考样例解释 

输入描述:

第一行一个整数N，表示数组长度。

接下来一行N个数表示数组内的数。

输出描述:

输出一个整数表示能装多少水。

示例1

输入

6
3 1 2 5 2 4

输出

5

说明

示例2

输入

5
4 5 1 3 2

输出

2

class Solution:
    def maxWater(self , arr ):
        # write code here
        if not arr:
            return 0
        left, right = 0, len(arr)-1
        left_val, right_val = arr[left], arr[right]
        max_water = 0
        while left < right:
            if left_val < right_val:
                left += 1
                if arr[left] >= left_val:
                    left_val = arr[left]
                    continue
                else:
                    max_water += (left_val - arr[left])
            else: 
                right -= 1
                if arr[right] >= right_val:
                    right_val = arr[right]
                    continue 
                else:
                    max_water += (right_val - arr[right])
                    
        return max_water
                        
                    
S = Solution()
while True:
    try:
        arr = list(map(int, input()[1:-1].split(',')))
        print(S.maxWater(arr))
    except:
        break