"""
two-pointers && slide-window

Medium:
到了Medium和Hard之后，有些题已经不单纯是双指针问题了。
可能有其他算法思想在其中，只不过是借用双指针/窗口的移动来解决问题

3. 无重复字符的最长子串
15. 三数之和
11. 盛最多水的容器 (这个其实不算双指针或窗口，这个本质是贪心)
"""

question_list = [3,]


"""
3. 无重复字符的最长子串 
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
"""
def lengthOfLongestSubstring(s):
    """
    滑动窗口题
    右侧遍历移动
    左侧遇到窗口内相同元素移动
    左侧移动距离需要靠窗口的map来查找
    """

    ret = 0
    left, right = 0, 0
    hm = {}
    while right < len(s):
        char = s[right]
        if char in hm and hm[char] >= left:
            left = hm[char] + 1
        else:
            if right - left + 1 > ret:
                ret = right - left + 1
        hm[char] = right
        right += 1
    return ret

"""
15. 三数之和
# 隐藏target=0
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
"""
def threeSum(nums):
    """
    1. 先排序!!，后固定第一个元素，用左右双指针求其余两个的和
    2. 注意跳过重复元素 外层第一个元素要跳，内层左右指针也要跳
    """
    nums.sort()
    ret = []
    for i, first in enumerate(nums):
        if i > 0 and first == nums[i - 1]:
            continue  # 第一个元素排重
        target = 0 - first
        left = i + 1
        right = len(nums) - 1
        while left < right:
            sumtwo = nums[left] + nums[right]
            if sumtwo < target:
                left += 1
            elif sumtwo > target:
                right -= 1
            else:
                ret.append([first, nums[left], nums[right]])
                left += 1
                right -= 1
                # 左右指针排重
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return ret

"""
11. 盛最多水的容器
"""
def maxArea(self, height):
    """
    本质是贪心：面积 = (j - i) * min(height_i, height_j)。
    实际是靠双指针对撞移动，每次移动短的那个（因为只有移动短的，下次的结果才有可能得到优化，这就是“贪心算法”）
    """
    i, j = 0, len(height) - 1
    ret = 0
    while i < j:
        if height[i] > height[j]:
            area = (j - i) * height[j]
            j -= 1
        else:
            area = (j - i) * height[i]
            i += 1

        if area > ret:
            ret = area
    return ret

"""
5. 最长回文子串
双指针****特殊****的一道题：双指针都起始在中间，向两个方向扩散移动。
这个题也适合DP[1][2]处理，完美符合模版，但空间复杂度不如双指针
"""
def longestPalindrome(self, s):
    """
    双指针都在中心点，向两个方向移动
    注意边界，切片左开右闭
    """
    # 辅助方法
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    ret = ""
    for i in range(len(s)):
        a = expand(i, i) # 奇数中心扩散的情况
        b = expand(i, i + 1) # 偶数中心扩散的情况
        if len(a) > len(ret):
            ret = a
        if len(b) > len(ret):
            ret = b
    return ret

"""
LCR 026. 重排链表
1. 可以先把链表装数组里之后用双指针对撞重新组合。时间O(n),空间O(n)
2. 也可以使用链表骚操作之：链表找中点（快慢指针）+ 后半段链表翻转 + 两个半链表合并， 这样的话空间复杂度是O(1), 
"""
def reorderList(self, head):
    """
    1. 先把链表装数组里
    2. 数组左右指针对撞
    """
    if not head:
        return

    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.next

    i, j = 0, len(nodes) - 1
    while i < j:
        if i == j - 1:
            nodes[i].next = nodes[j]
            nodes[j].next = None
        elif i == j - 2:
            nodes[i].next = nodes[j]
            nodes[j].next = nodes[i + 1]
            nodes[i + 1].next = None
        else:
            nodes[i].next = nodes[j]
            nodes[j].next = nodes[i + 1]
        i += 1
        j -= 1
    return

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

这跟双指针没啥关系啊，纯纯链表操作。
"""
def removeNthFromEnd(self, head, n):
    """
    先装列表，然后操作。
    边界case穷举处理。
    """
    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.next

    if n > len(nodes):
        return None

    nxt = nodes[-n].next
    if n == len(nodes):
        return nxt
    pre = nodes[-(n + 1)]
    pre.next = nxt
    return nodes[0]

# 这才是双指针解法：快慢指针。
# 1. 倒数第N个，就是还差N个到终点。
# 2. 如果a先走N个，b在开始走，a到终点的时候，b正好差N个
# 3. 注意下边界case（n可能是走了n+1， 仔细想想）
def removeNthFromEnd2(head, n):
        dummy = ListNode(0, head)
        i = 0
        slow, fast = dummy, dummy
        while i < n + 1:
            fast = fast.next
            i += 1

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next