leetcode #1 兩數(shù)之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = dict()
        for i, val in enumerate(nums):
            dic[val] = i
        for i, val in enumerate(nums):
            j = dic.get(target-val)
            if j and j != i:
                return [i, j]

leetcode #15 三數(shù)之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚舉 a
        for first in range(n):
            # 需要和上一次枚舉的數(shù)不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 對應(yīng)的指針初始指向數(shù)組的最右端
            third = n - 1
            target = -nums[first]
            # 枚舉 b
            for second in range(first + 1, n):
                # 需要和上一次枚舉的數(shù)不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保證 b 的指針在 c 的指針的左側(cè)
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指針重合，隨著 b 后續(xù)的增加
                # 就不會有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

leetcode #15 最接近的三數(shù)之和
排序后雙指針法

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        best = 10**7
        
        # 根據(jù)差值的絕對值來更新答案
        def update(cur):
            nonlocal best
            if abs(cur - target) < abs(best - target):
                best = cur
        
        # 枚舉 a
        for i in range(n):
            # 保證和上一次枚舉的元素不相等
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 使用雙指針枚舉 b 和 c
            j, k = i + 1, n - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                # 如果和為 target 直接返回答案
                if s == target:
                    return s
                update(s)
                if s > target:
                    # 如果和大于 target，移動 c 對應(yīng)的指針
                    k0 = k - 1
                    # 移動到下一個不相等的元素
                    while j < k0 and nums[k0] == nums[k]:
                        k0 -= 1
                    k = k0
                else:
                    j0 = j + 1
                    while k > j0 and nums[j0] == nums[j]:
                        j0 += 1
                    j = j0
        return best

leetcode #18 四數(shù)之和
與三數(shù)之和類似

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)  #先排序
        if n<4:
            return []
        nums.sort()
        res = []
        for i in range(n-3):
            if i>0 and nums[i]==nums[i-1]:continue #第一個元素向后遍歷時如果和當(dāng)前元素相等則越過
            if nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:break #如果升序數(shù)組前四個數(shù)已經(jīng)比target大，則說明后續(xù)不會有結(jié)果，直接返回空列表
            if nums[i]+nums[n-3]+nums[n-1]+nums[n-2]<target:continue #如果當(dāng)前第一個元素和最后三個元素之和小于target，第一個元素往后移一位
            for j in range(i+1,n-2):
                if j>i+1 and nums[j]==nums[j-1]:continue # 第二個元素同理第一個元素
                if nums[i]+nums[j+1]+nums[j+2]+nums[j]>target:break
                if nums[i]+nums[n-2]+nums[n-1]+nums[j]<target:continue
                left,right = j+1,n-1#第三第四個元素同雙指針
                while left<right:
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    if tmp == target: #遇到合法結(jié)果，append當(dāng)前四個元素
                        res.append([nums[i],nums[j],nums[left],nums[right]])   
                        #left和right分別向右向左走找到與當(dāng)前第三第四個元素不同的元素
                        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 
                    # 如果當(dāng)前結(jié)果大于targe，右指針向左走
                    elif tmp > target: right -= 1 
                    # 如果當(dāng)前結(jié)果小于target，左指針向右走
                    else: left += 1

        return res

leetcode #49 字母異位詞分組
考慮將每個字符串按字母大小排序，之后利用哈希表實現(xiàn)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = dict()
        for s in strs:
            sorted_s = ''.join(sorted(s))
            if sorted_s not in hashmap:
                hashmap[sorted_s] = [s]
            else:
                hashmap[sorted_s].append(s)

        return [hashmap[key] for key in hashmap]

leetcode #149

leetcode #219 存在重復(fù)元素2

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        hashmap = dict()
        for i in range(len(nums)):
            if nums[i] not in hashmap:
                hashmap[nums[i]] = i
            else:
                if i - hashmap[nums[i]] <= k:
                    return True
                else:
                    hashmap[nums[i]] = i
        return False

leetcode #220 存在重復(fù)元素3

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if t < 0 or not k or not nums:
            return False

        if k == 1:
            for i in range(len(nums)-1):
                if abs(nums[i]-nums[i+1]) <= t:
                    return True
            return False

        if not t:
            dct = {}
            for inx, i in enumerate(nums):
                if i in dct:
                    if inx-dct[i] <= k:
                        return True
                dct[i] = inx
            return False

        lst = []
        i = nums[0]
        lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))

        for i in nums[1:]:
            if i in set(sum(lst, ())):
                return True
            lst.append(sum([(i-j, i+j) for j in range(t+1)], ()))
            lst = lst[-k:]

        return False

leetcode #447 回旋鏢

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        count = 0
        for i in range(len(points)):
            hashmap = dict()
            x, y = points[i]
            for j in range(len(points)):
                if i == j:
                    continue
                x_, y_ = points[j]
                dis = (x-x_)**2 + (y-y_)**2
                if dis not in hashmap:
                    hashmap[dis] = [j]
                else:
                    hashmap[dis].append(j)
            for key in hashmap:
                k = len(hashmap[key])
                if k >= 2:
                    count += k * (k-1)
        return count

leetcode #454 四數(shù)相加2

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        n = len(A)
        if n == 0:
            return 0
        hashmap = dict()
        count = 0
        for i in range(n):
            for j in range(n):
                if A[i]+B[j] not in hashmap:
                    hashmap[A[i]+B[j]] = 1
                else:
                    hashmap[A[i]+B[j]] += 1
        for i in range(n):
            for j in range(n):
                if -(C[i]+D[j]) in hashmap:
                    count += hashmap[-(C[i]+D[j])]
        return count