leetcode-python-day10-第18题

========坚持30天刷leetcode=====

题目链接：https://leetcode-cn.com/problems/4sum/

分析：

本题的解题思路与上一题类似，排序，然后先固定几个位置，再首尾各一个变量移动遍历。关键在于：特殊情况的判别，从而降低时间复杂度。

            
              class Solution:
    def fourSum(self, nums, target):
        k=len(nums)
        if k<4: return None           # 特殊情况： 数组小于4
        if k==4 and sum(nums)==target: return [nums]     # 特殊情况： 数组等于4
        nums.sort()
        if nums[0]*4> target:     # 特殊情况： 最小4个数和 大于target
            return []
        if nums[k-1]*4
              
                target:
                break
            if nums[a]+nums[k-3]+nums[k-2]+nums[k-1]
                
                  target:
                    break
                if nums[a]+nums[b]+nums[k-2]+nums[k-1]
                  
                    < d and nums[c-1] == nums[c]: c+= 1
                        d-=1
                        while c < d and nums[d] == nums[d+1]: d-= 1 
                    elif nums[a]+nums[b]+nums[c]+nums[d]
                    
                      < d and nums[c-1] == nums[c]: c+= 1    
                    else:                                                # 移动 d     
                        d-=1
                        while c < d and nums[d] == nums[d+1]: d-= 1    
        return result