Problem: 454. 四数相加 II

思路

讲述看到这一题的思路

• 思考: 如何用map有效节省时间

想一想: 题目1.两数之和, 用的map

• 推广: 可以时间O(n^3),空间O(n)

map: key=sum123, val=times

• 推广: 时间O(n^2), 空间O(n^2)

两两构建map: key=sum12, val=times

遍历一个map, 检索另一个

• 优化: 时间O(n^2), 空间O(n^2)

构建1个map: key=sum12, val=times

遍历一个map, 检索另一个

知识补充

• 补充: dict.get(key, 缺省值)

Code

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        
        m = {} # 存储

        # 遍历nums1和nums2构建map
        for i in nums1:
            for j in nums2:
                if i+j not in m:
                    m[i+j] = 1
                else:
                    m[i+j] += 1
                    
        n = 0
        # 遍历nums3和nums4并且检索map
        for i in nums3:
            for j in nums4:
                n += m.get(-i-j, 0) # 补充: dict.get(key, 缺省值)

        return n

Problem: 383. 赎金信

思路

讲述看到这一题的思路

用len=26的数组l: idx表示alpha, val表示个数

遍历magazine, 得到l

遍历ransomNote, 对应l项–, 若对应项为0则false

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(n)$

• 空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # 用len=26的数组l: idx表示alpha, val表示个数
        # 遍历magazine, 得到l
        # 遍历ransomNote, 对应l项--, 若对应项为0则false

        # 构建hash
        l = [0] * 30
        for ch in magazine:
            l[ord(ch) - ord('a')] += 1
        
        # 检索
        for ch in ransomNote:
            if l[ord(ch) - ord('a')] > 0:
                l[ord(ch) - ord('a')] -= 1
            else: 
                return False
        
        return True

Problem: 15. 三数之和

时间
644 ms
击败
70.10%
内存
18 MB
击败
21.40%

思路

讲述看到这一题的思路

思路: 双指针, 时间O(n^2)

1. 进行排序

2. 双指针: first,mid,end

   遍历first, 向后移动mid或者向前移动end

   重点:如何去重

    因为已经sort
    所以可以直接通过移动, 排除掉连续相同的数
   

复杂度

• 时间复杂度:

添加时间复杂度, 示例： $O(n^2)$

• 空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 思路: 双指针, 时间O(n^2)
        # 1.进行排序
        # 2.双指针: first,mid,end
        #   遍历first, 向后移动mid或者向前移动end
        #   重点:如何去重
        #       因为已经sort
        #       所以可以直接通过移动, 排除掉连续相同的数

        # 先进行排序
        nums.sort()
        print(nums)

        l = []

        # 遍历
        first = 0
        while first < len(nums) - 2:
            if nums[first] > 0: # 因为非递减 => first大于0, 不可能总和等于0
                return l

            # 初始化双指针
            mid = first + 1
            end = len(nums) - 1

            while end > mid:
                # 移动双指针
                if nums[first]+nums[mid]+nums[end] < 0:
                    mid += 1
                    continue
                if nums[first]+nums[mid]+nums[end] > 0:
                    end -= 1
                    continue
                
                if nums[first]+nums[mid]+nums[end] == 0:
                    print("find:",first,mid,end)
                    # 在找到3元组之后再进行去重
                    while end > 0 and nums[end] == nums[end - 1]:
                        end -= 1
                    while mid < len(nums)-1 and nums[mid] == nums[mid + 1]:
                        mid += 1
                    l.append([nums[first],nums[mid],nums[end]])
                    # 共同向中间移动
                    mid += 1
                    end -= 1
            
            # 对于first进行去重
            while first < len(nums)-1 and nums[first] == nums[first + 1]:
                first += 1
            first += 1

        return l

Problem: 18. 四数之和

Code

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        l = []
        i = 0
        while i < len(nums)-3:
            print()
            print("i=",i)
            if nums[i] > 0 and nums[i] > target: # 剪枝
                return l
            j = i+1
            while j < len(nums)-2:
                if nums[i]+nums[j] > 0 and nums[i]+nums[j] > target: # 剪枝
                    break
                left = j+1
                right = len(nums)-1

                # 双指针
                while left < right:
                    if nums[i]+nums[j]+nums[left]+nums[right] > target:
                        right -= 1
                        continue
                    elif nums[i]+nums[j]+nums[left]+nums[right] < target:
                        left += 1
                        continue
                    else: # 找到了, 进行去重
                        l.append([nums[i],nums[j],nums[left],nums[right]])
                        while left < len(nums)-1 and nums[left] == nums[left+1]:
                            left += 1
                        while right > left and nums[right] == nums[right-1]:
                            right -= 1
                        left += 1
                        right -= 1
                    
                # j去重
                while j < len(nums)-1 and nums[j] == nums[j+1]:
                    j += 1
                j += 1
            
            # i去重
            while i < len(nums)-1 and nums[i] == nums[i+1]:
                i += 1
            i += 1
        
        return l         

原文地址：http://www.cnblogs.com/ywh-pku/p/16847606.html