LeetCode刷题记录2020-10-05之Double Pointer！！！

题目一：

454. 四数相加 II

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        # 字典两两进行微处理
        count = 0
        d = {}
        for i in range(len(A)):
            for j in range(len(B)):
                tmp = A[i] + B[j]
                if d.get(tmp) is not None:
                    d[tmp] += 1
                else:
                    d[tmp] = 1
        for i in range(len(C)):
            for j in range(len(D)):
                tmp = C[i] + D[j]
                if d.get(-tmp) is not None:
                    count += d[-tmp]
        return count

题目二：

1. 两数之和

def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        res = []
        for i in range(len(nums)):
            # 不能是d.get(nums[i]), 当下标为0时，是个坑
            # 用d.get(nums[i]) is not None来判断
            if d.get(nums[i]) is not None:
                res = [d[nums[i]], i]
                break
            else:
                d[target - nums[i]] = i
        return res

题目三：

15. 三数之和

def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        lenth = len(nums)
        nums.sort()
        for p in range(len(nums) - 2):
            # 1.满足什么条件直接跳出循环(p < i < j)
            if nums[p] > 0: break

            # 2.满足什么条件跳过当前循环(去重)
            if p > 0 and nums[p] == nums[p-1]: continue

            # 3.双指针(double pointer)
            i = p + 1
            j = lenth - 1
            while i < j:
                num = nums[p] + nums[i] + nums[j]
                if num < 0:
                    i += 1
                elif num > 0:
                    j -= 1
                else:
                    res.append([nums[p], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i-1]:
                        i += 1
                    while i < j and nums[j] == nums[j+1]:
                        j -= 1
        return res

题目四：

18. 四数之和

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 0. nums排序
        # 1. 提前结束break: 根据题意来
        # 2. 去重continue: nums[p] == nums[p-1]
        # 3. 双指针遍历：double pointer

        lenth = len(nums)
        res = []
        nums.sort()

        # k, p, i, j
        for k in range(len(nums) - 3):
            # 1
            if nums[k] + 3 * nums[k+1] > target: break
            # 2
            if (k > 0 and nums[k] == nums[k-1]) or nums[k] + 3 * nums[-1] < target: continue
            # 3 -> 1
            for p in range(k+1, len(nums) - 2):
                # 1
                if nums[k] + nums[p] + 2*nums[p+1] > target: break
                # 2
                if (p > k+1 and nums[p] == nums[p-1]) or nums[k] + nums[p] + 2 * nums[-1] < target: continue
                # 3
                i = p+1
                j = lenth - 1
                while i < j:
                    num = nums[k] + nums[p] + nums[i] + nums[j]
                    if num < target:
                        i += 1
                    elif num > target:
                        j -= 1
                    else:
                        res.append([nums[k],nums[p], nums[i], nums[j]])
                        i += 1
                        j -= 1
                        while i < j and nums[i] == nums[i - 1]: i += 1
                        while i < j and nums[j] == nums[j + 1]: j -= 1
        return res