Python力扣刷题06- 四数相加&赎金信&三数之和&四数之和

小咪咪 2023-09-28 23:21 84阅读 0赞

##  ##

### **454.四数相加II** ###

题目链接：[https://leetcode.cn/problems/4sum-ii/][https_leetcode.cn_problems_4sum-ii]

题目描述：给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n  
nums1\[i\] + nums2\[j\] + nums3\[k\] + nums4\[l\] == 0

案例：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
    输出：2
    解释：
    两个元组如下：
    1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
    
    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/4sum-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

实现：

class Solution:
        def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
            hashmap = dict()
            for n1 in nums1:
                for n2 in nums2:
                    if n1 + n2 in hashmap:
                        hashmap[n1+n2] += 1
                    else:
                        hashmap[n1+n2] = 1
            count = 0
            for n3 in nums3:
                for n4 in nums4:
                    key = 0-(n3+n4) # 0-(n3+n4) = n1+n2,即n1+n2+n3+n4=0
                    if key in hashmap:
                        count += hashmap[key]
            return count

### **383. 赎金信** ###

题目链接：[https://leetcode.cn/problems/ransom-note/）][https_leetcode.cn_problems_ransom-note]

题目描述：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

案例：

输入：ransomNote = "a", magazine = "b"
    输出：false
    
    输入：ransomNote = "aa", magazine = "aab"
    输出：true

实现：

class Solution:
        def canConstruct(self, ransomNote: str, magazine: str) -> bool:
            c1 = collections.Counter(ransomNote)
            c2 = collections.Counter(magazine)
            x = c1 -c2
            if(len(x)==0):
                return True
            else:
                return False

### **15. 三数之和** ###

题目链接：[https://leetcode.cn/problems/3sum/][https_leetcode.cn_problems_3sum]

题目描述：给你一个整数数组 nums ，判断是否存在三元组 \[nums\[i\], nums\[j\], nums\[k\]\] 满足 i != j、i != k 且 j != k ，同时还满足 nums\[i\] + nums\[j\] + nums\[k\] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

案例：

输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]
    解释：
    nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    注意，输出的顺序和三元组的顺序并不重要。

解题思路来源于K神：

链接：https://leetcode.cn/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/

双指针法铺垫： 先将给定 nums 排序，复杂度为 O(NlogN)  
双指针法思路： 固定 33 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums\[k\] + nums\[i\] + nums\[j\] == 0 的 i,j 组合：

*  1.当 nums\[k\] > 0 时直接break跳出：因为 nums\[j\] >= nums\[i\] >= nums\[k\] > 0，即 33 个数字都大于 00 ，在此固定指针 k 之后不可能再找到结果了。
 *  2.当 k > 0且nums\[k\] == nums\[k - 1\]时即跳过此元素nums\[k\]：因为已经将 nums\[k - 1\] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
 *  3.i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums\[k\] + nums\[i\] + nums\[j\]，并按照以下规则执行双指针移动：
    
     *  当s < 0时，i += 1并跳过所有重复的nums\[i\]；
     *  当s > 0时，j -= 1并跳过所有重复的nums\[j\]；
     *  当s == 0时，记录组合\[k, i, j\]至res，执行i += 1和j -= 1并跳过所有重复的nums\[i\]和nums\[j\]，防止记录到重复组合。

实现：

class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            res,k = [],0
            n = len(nums)
            for k in range(n - 2):
                # k>0,那么j>i>k三个值都会>0，直接跳过
                if nums[k] > 0: break
                # 跳过相同的k
                if k > 0 and nums[k] == nums[k-1]: continue
                i,j = k+1, n-1
    
                while i < j:
                    s = nums[k] + nums[i] + nums[j]
                    # 当总数小于0的时候，要让它变大，所以需要让左边的i值变大，即i+1
                    if s < 0:
                        i += 1
                        while i < j and nums[i] == nums[i - 1]: i += 1
                    # 当总数大于0的时候，要让它变小，所以需要让右边的j值变小，即j-1
                    elif s>0:
                        j -= 1
                        while i < j and nums[j] == nums[j + 1]: j -= 1
                    else:
                        res.append([nums[k],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. 四数之和** ###

题目链接：[https://leetcode.cn/problems/4sum/][https_leetcode.cn_problems_4sum]

题目描述：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 \[nums\[a\], nums\[b\], nums\[c\], nums\[d\]\] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n  
a、b、c 和 d 互不相同  
nums\[a\] + nums\[b\] + nums\[c\] + nums\[d\] == target  
你可以按 任意顺序 返回答案 。

案例：

输入：nums = [1,0,-1,0,-2,2], target = 0
    输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

实现：

# 双指针法
    class Solution:
        def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
            
            nums.sort()
            n = len(nums)
            res = []
            for i in range(n):
                if i > 0 and nums[i] == nums[i - 1]: continue
                for k in range(i+1, n):
                    if k > i + 1 and nums[k] == nums[k-1]: continue
                    p = k + 1
                    q = n - 1
    
                    while p < q:
                        if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                        elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                        else:
                            res.append([nums[i], nums[k], nums[p], nums[q]])
                            while p < q and nums[p] == nums[p + 1]: p += 1
                            while p < q and nums[q] == nums[q - 1]: q -= 1
                            p += 1
                            q -= 1
            return res

[https_leetcode.cn_problems_4sum-ii]: https://leetcode.cn/problems/4sum-ii/
[https_leetcode.cn_problems_ransom-note]: https://leetcode.cn/problems/ransom-note/
[https_leetcode.cn_problems_3sum]: https://leetcode.cn/problems/3sum/
[https_leetcode.cn_problems_4sum]: https://leetcode.cn/problems/4sum/