【700】Leecode solution

15. 三数之和

　　可以通过双指针的方式来降低时间复杂度！

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        arr = []
        length = len(nums)
        nums.sort() 

        for i in range(length-2):
            if nums[i] > 0: break
            if i > 0 and nums[i] == nums[i-1]: continue 
            left = i + 1
            right = length - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    arr.append([nums[i], 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
                elif s < 0:
                    left += 1
                    while(left < right and nums[left] == nums[left - 1]): left += 1
                else:
                    right -= 1
                    while(left < right and nums[right] == nums[right + 1]): right -= 1

        return arr

16. 最接近的三数之和

　　可以通过双指针的方式来降低时间复杂度！

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = nums[0] + nums[1] + nums[-1]
        gap = abs(res - target)

        for i in range(len(nums) - 2):
            if nums[i] > 0 and nums[i] > target: break
            left = i + 1
            right = len(nums) - 1

            while(left < right):
                s = nums[i] + nums[left] + nums[right]
                if s == target:
                    return target
                elif s < target:
                    if target - s < gap:
                        gap = target -s
                        res = s 
                    left += 1
                else:
                    if s - target < gap:
                        gap = s - target
                        res = s 
                    right -= 1

        return res

17. 电话号码的字母组合

　　使用动态规划的方法来解决！

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        hashmap = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
                   "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        dp = [[] for i in range(len(digits) + 1)]
        dp[1] = [e for e in hashmap[digits[0]]]

        for i in range(2, len(digits)+1):
            arr = []
            for e1 in dp[i-1]:
                for e2 in hashmap[digits[i-1]]:
                    arr.append(e1+e2)
            dp[i] = arr 

        return dp[-1]

18. 四数之和

　　双指针的方法！

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []

        for i in range(len(nums)-3):
            if nums[i] > 0 and nums[i] > target: continue
            for j in range(i+1, len(nums)-2):
                if nums[j] > 0 and nums[i] + nums[j] > target: continue
                left = j + 1
                right = len(nums) - 1

                while(left < right):
                    s = nums[i] + nums[j] + nums[left] + nums[right]
                    if s == target:
                        tmp = [nums[i], nums[j], nums[left], nums[right]]
                        if tmp not in res: res.append(tmp)
                        left += 1
                        right -= 1
                    elif s < target:
                        left += 1
                    else:
                        right -= 1

        return res