Python 76 ms beats 97.09%, explain why it is fast.
Problem:\n\n> Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all uniq
# Problem:\n\n> Given an array `nums` of *n* integers and an integer `target`, are there elements *a*, *b*, *c*, and *d* in `nums` such that *a* + *b* + *c* + *d* = `target`? Find all unique quadruplets in the array which gives the sum of `target`. The solution set must not contain duplicate quadruplets.\n\nExample :\n\n\n```\nGiven array nums = [1, 0, -1, 0, -2, 2], and target = 0.\n\nA solution set is:\n[\n  [-1,  0, 0, 1],\n  [-2, -1, 1, 2],\n  [-2,  0, 0, 2]\n]\n```\n\n## Solution 1\n\n```python\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        nums.sort()\n        i = 0\n        L = len(nums)\n        res = []\n        while i < L-3:\n            j = i+1\n            while j < L-2:\n                left = j+1\n                right = L-1\n                new_target = target-nums[i]-nums[j]\n                while left<right:\n                    if nums[left]+nums[right] > new_target:\n                        right-=1\n                    elif nums[left]+nums[right] < new_target:\n                        left+=1\n                    else:\n                        res.append([nums[i],nums[j],nums[left],nums[right]])\n                        temp_left = nums[left]\n                        temp_right = nums[right]\n                        while(left<right and nums[left]==temp_left):\n                            left+=1\n                        while(left<right and nums[right]==temp_right):\n                            right-=1\n                while j < L-3 and nums[j] == nums[j+1]:\n                    j+=1\n                j+=1\n            while i < L-4 and nums[i] == nums[i+1]:\n                i+=1\n            i+=1\n        return res\n```\n> Runtime: 880 ms; Memory Usage: 12.8 MB\n\n## Solution 2\n\n```python\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        nums.sort()\n        res = []\n        self.findNSum(nums, target, 4, [], res)\n        return res\n\n    def findNSum(self, nums, target, N, prefix, result):\n        L = len(nums)\n        if N == 2:\n            l, r = 0, L-1\n            while l < r:\n                add = nums[l] + nums[r]\n                if add == target:\n                    result.append(prefix + [nums[l], nums[r]])\n                    l += 1\n                    r -= 1\n                    while l<r and nums[l-1] == nums[l]:\n                        l += 1\n                    while l<r and nums[r+1] == nums[r]:\n                        r -= 1\n                elif add > target:\n                    r -= 1\n                else:\n                    l += 1\n        else:\n            for i in range(L-N+1):\n                if target < N*nums[i] or target > N*nums[-1]: # key judgement\n                    break\n                if i == 0 or (i>0 and nums[i] != nums[i-1]):\n                    self.findNSum(nums[i+1:], target-nums[i], N-1, prefix+[nums[i]], result)\n        return\n```\n> Runtime: 84 ms; Memory Usage: 12.8 MB\n\n## Solution 3\n\n```python\nclass Solution:\n    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n        nums.sort()\n        i = 0\n        L = len(nums)\n        res = []\n        while i < L-3:\n            if target-nums[i] < 3*nums[i+1] or target-nums[i] > 3*nums[-1]:\n                    while i < L-4 and nums[i] == nums[i+1]:\n                        i+=1\n                    i+=1\n                    continue\n            j = i+1\n            while j < L-2:\n                if target-nums[i]-nums[j] < 2*nums[j+1] or target-nums[i]-nums[j] > 2*nums[-1]:\n                    while j < L-3 and nums[j] == nums[j+1]:\n                        j+=1\n                    j+=1\n                    continue\n                left = j+1\n                right = L-1\n                new_target = target-nums[i]-nums[j]\n                while left<right:\n                    if nums[left]+nums[right] > new_target:\n                        right-=1\n                    elif nums[left]+nums[right] < new_target:\n                        left+=1\n                    else:\n                        res.append([nums[i],nums[j],nums[left],nums[right]])\n                        temp_left = nums[left]\n                        temp_right = nums[right]\n                        while(left<right and nums[left]==temp_left):\n                            left+=1\n                        while(left<right and nums[right]==temp_right):\n                            right-=1\n                while j < L-3 and nums[j] == nums[j+1]:\n                    j+=1\n                j+=1\n            while i < L-4 and nums[i] == nums[i+1]:\n                i+=1\n            i+=1\n        return res\n```\n> Runtime: 76 ms; Memory Usage: 12.8 MB\n\n## Note:\n\n- \u5728\u7B2C\u4E8C\u79CD\u7B97\u6CD5\u662F\u9012\u5F52\u7B97\u6CD5\u3002\n- \u7B2C\u4E8C\u79CD\u7B97\u6CD5\u6BD4\u7B2C\u4E00\u79CD\u7B97\u6CD5\u5FEB\u5728`line 28`\uFF0C\u5373\u5173\u952E\u5224\u65AD\u3002\n- \u7B2C\u4E09\u79CD\u7B97\u6CD5\u662F\u5728\u7B2C\u4E00\u79CD\u7B97\u6CD5\u7684\u57FA\u7840\u4E0A\u589E\u52A0\u4E86\u5173\u952E\u5224\u65AD\uFF0C\u901F\u5EA6\u5F97\u5230\u5927\u5E45\u63D0\u5347\u3002\u5E76\u4E14\u6BD4\u9012\u5F52\u7B97\u6CD5\u66F4\u5FEB\u3002\n- Solution 2 is recursive algorithm.\n- Solution 2 is faster than solution 1 because of `line 28`, which is the key judgement.\n- Adding the key judgement to solution1 makes solution 3, which is even faster than recursive algorithm solution 2.
['Python', 'Python3']