题目：
    给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 ：整数，并返回它们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
    你可以按任意顺序返回答案。

示例：
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

# 暴力解法复杂度过高
# 所以借助哈希表
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

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

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

示例：
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

# n**2 一个循环然后 left right双指针夹逼
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        l = len(nums)
        res = []
        if l <= 2:
            return res
        nums.sort()
        for i in range(l):
            if nums[i]>0:
                return res
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = l -1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    while left + 1 < right and nums[left] == nums[left + 1]:
                        left += 1
                    while right -1 > left and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        return res

题目：
    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
    输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = float('inf')
        
        # 根据差值的绝对值来更新答案
        def update(cur):
            nonlocal best
            if abs(cur - target) < abs(best - target):
                best = cur
        
        # 枚举 a
        for i in range(n-2):
            # 保证和上一次枚举的元素不相等
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 使用双指针枚举 b 和 c
            left, right = i + 1, n - 1
            while left < right:
                real = nums[i] + nums[left] + nums[right]
                # 如果和为 target 直接返回答案
                if real == target:
                    return target
                update(real)
                if real > target:
                    # 如果和大于 target，移动 c 对应的指针
                    right_tmp = right - 1
                    # 移动到下一个不相等的元素
                    while right_tmp > left and nums[right_tmp] == nums[right]:
                        right_tmp -= 1
                    right = right_tmp
                else:
                    # 如果和小于 target，移动 b 对应的指针
                    left_tmp = left + 1
                    # 移动到下一个不相等的元素
                    while left_tmp < right and nums[left_tmp] == nums[left]:
                        left_tmp += 1
                    left = left_tmp
        return best

题目：
    给定一个长度为 n 的整数数组和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组  i, j, k 个数（0 <= i < j < k < n）。
示例：
    输入: nums = [-2,0,1,3], target = 2
    输出: 2 
    解释: 因为一共有两个三元组满足累加和小于 2:
         [-2,0,1]
         [-2,0,3]

# 借鉴了left right但是只打败了20% 不可取
class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        length = len(nums)
        res = 0
        for i in range(length-2):
            left, right = i + 1, length -1
            while left < right:
                if nums[i]+nums[left]+nums[right]>=target:
                    right -= 1
                else:
                    res += (right-left)
                    left += 1
        return res

题目：
    给你一个由 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
    你可以按 任意顺序 返回答案 。

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

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

# 借鉴了（15. 三数之和），多了一个循环
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        length = len(nums)
        mark=0
        for i in range(length-3):
            if i -1 >= 0 and nums[i-1] == nums[i]:
                # mark += 1
                # print(mark,'i',i)
                continue
            for j in range(i+1, length-2):
                if j-1 >=i+1 and nums[j-1] == nums[j]:
                    # mark += 1
                    # print(mark,'i',i,'j',j)
                    continue
                left = j + 1
                right = length - 1
                while left < right:
                    dif = nums[i]+nums[j]+nums[left]+nums[right]-target
                    if dif == 0 :
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        while left + 1 < right and nums[left] == nums[left + 1]:
                            left += 1
                        while right -1 > left and nums[right] == nums[right - 1]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif dif > 0:
                        right -= 1
                    else:
                        left += 1
                    
        return res