一、最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        result=nums[0]+nums[1]+nums[2]
        minus=abs(nums[0]+nums[1]+nums[2]-target)
        for i in range(len(nums)-2):
            left,right=i+1,len(nums)-1

            while left<right:
                total=nums[i]+nums[left]+nums[right]
                gap=abs(total-target)
                if gap<minus:
                    result=total
                    minus=gap
                if total<target:
                    left+=1
                elif total>target:
                    right-=1
                else:
                    return total
        return result

二、四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if not nums or len(nums)<4:
            return []
        
        nums.sort()
        result=[]
        n=len(nums)
        for i in range(n-3):
            #修枝
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:
                break
            if nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target:
                continue
            #去重
            if i>0 and nums[i]==nums[i-1]:
                continue
            for j in range(i+1,n-2):
                #修枝
                if nums[i]+nums[j]+nums[j+1]+nums[j+2]>target:
                    break
                if nums[i]+nums[j]+nums[n-1]+nums[n-2]<target:
                    continue
                #去重
                if j>i+1 and nums[j]==nums[j-1]:
                    continue
                left,right=j+1,n-1
                while left<right:
                    total=nums[i]+nums[j]+nums[left]+nums[right]
                    if total<target:
                        left+=1
                    elif total>target:
                        right-=1
                    else:
                        result.append([nums[i],nums[j],nums[left],nums[right]])
                        while left<right and nums[left]==nums[left+1]:
                            left+=1
                        while left>right and nums[right]==nums[right-1]:
                            right-=1
                        left+=1
                        right-=1
        return result

三、删除列表的倒数第N个结点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        #创建两个指针，都指向头结点
        first=head
        second=head

        for i in range(n):
            first=first.next
        
        if first is None:
            return head.next
        
        while first.next is not None:
            first=first.next
            second=second.next

        second.next=second.next.next

        return head