刷题日记 Day 6 : 四数相加 II、赎金信、三数之和、四数之和

左手的ㄟ右手 2024-03-26 21:19 58阅读 0赞

#### 刷题日记 Day 6 ####

*  一 . LeetCode 454 . 四数相加 II
 *  二 . LeetCode 383 . 赎金信
 *  三 . LeetCode 15 . 三数之和
 *  四 . LeetCode 18 . 四数之和

> 本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解  
> 参与链接在此 : [https://programmercarl.com/other/xunlianying.html][https_programmercarl.com_other_xunlianying.html]

> 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个专栏想要帮助大家摆脱困境 , 横扫饥饿 , 做回自己 . 让大家掌握最常见的面试题 , 面对陌生的题目也不至于无从下手 .  
> 也希望大家监督 , 60 天从 0 到 1 , 咱们一起做大佬 ~  
> 今天是 Day6 , 大家加油~  
> ![image.png][]  
> 专栏链接 : [https://blog.csdn.net/m0\_53117341/category\_12247938.html?spm=1001.2014.3001.5482][https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]  
> 昨天的打卡链接 : [http://t.csdn.cn/XkRlf][http_t.csdn.cn_XkRlf]

## 一 . LeetCode 454 . 四数相加 II ##

题目链接 : [454. 四数相加 II][454. _ II]  
这道题也是考察哈希表的一道习题 , 他是在我们之前做过的有效的字母异位词的基础上进行加难度的  
我们来看思路  
![image.png][image.png 1]  
这道题 , 大家再仔细琢磨一下 , 实际上就是在有效字母异位词的基础上的一道题  
代码也在下面了

class Solution {
        
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        
            // 1. 创建一个 HashMap, key 存放 a+b 的值, value 存放 a+b 出现的次数
            Map<Integer,Integer> countMap = new HashMap<>();
            // 2. 定义答案变量,满足 a+b+c+d=0 的,ans++
            int ans = 0;
            // 3. 先遍历前两个数组,将两个数组每个元素都分别相加然后存入到 HashMap 中
            for(int a : nums1) {
        
                for(int b : nums2) {
        
                    int tmp = a + b;
                    // 不存在的话,要先将该值加入到哈希表中
                    if(!countMap.containsKey(tmp)) {
        
                        countMap.put(tmp,1);
                    } else {
         // 存在的话,拿出哈希表中存在的 value, 然后+1
                        countMap.put(tmp,countMap.get(tmp) + 1);
                    }
                }
            }
    
            // 4. 再遍历后两个数组
            for(int c : nums3) {
        
                for(int d : nums4) {
        
                    // 为了要求 a+b+c+d=0 的值,我们刚才已经求出了a+b的值,接下来就去找a+b的相反数,相加就等于0了
                    int target = - (c + d);
                    // 如果哈希表中存在  - (c + d),那就去加 target 出现的次数
                    if(countMap.containsKey(target)) {
        
                        // 注意此处不是 ans+=1;
                        // 因为等于target的值可能出现了很多次
                        ans += countMap.get(target);
                    }
                }
            }
    
            return ans;
        }
    }

## 二 . LeetCode 383 . 赎金信 ##

题目链接 : [383. 赎金信][383.]  
这道题实际上跟我们之前的有效字母异位词思路是一样的  
题目要求判断 ransomNote 能不能由 magazine 里面的字符构成  
那我们就先把 magazine 每个字母都映射到数组中 , 该数组负责统计对应字母出现的次数 , 遇到某字母 , 那就让他的 ASCII 下标对应的数字++  
接下来再去遍历 ransomNote 每个字母 , 让对应字母的 ASCII 下标 –  
最后我们去看一下 , ransomNote 的每个字母对应的 ASCII 下标是不是 < 0 , < 0 就代表 ransomNote 中有 magazine 里面的字符 , 就不能由 magazine 组成  
举个栗子 :  
栗子 1  
ransomNote = “a”, magazine = “b”  
刚开始遍历 magazine , 就将 b 对应的 ASCII 下标++

接下来 , 遍历 ransomNote , 将 a 对应的 ASCII 下标 –

接下来 , 再去遍历 ransomNote , 判断 a 对应的下标是不是 <0 , 小于 0 就代表 magazine 里面没有 a 这个字母  
栗子 2  
ransomNote = “aa”, magazine = “aab”  
先遍历 magazine , 将 magazine 里面每个字母存入到数组中

接下来再去遍历 ransomNote , 将 ransomNote 里面的每个字母对应的 ASCII 下标 –

接下来 , 再去遍历 ransomNote , 判断 ransomNote 每个字母对应的下标是不是 <0 , 小于 0 就代表 magazine 里面没有这个字母

--------------------

这道题就不给大家画图描述了 , 直接上代码~

class Solution {
        
        // 判断 ransomNote 能不能由 magazine 里面的字符构成
        // 所以先将 maganize 里面的元素存到数组中
        public boolean canConstruct(String ransomNote, String magazine) {
        
            // 1. 创建一个长度为 26 的数组
            int[] ans = new int[26];
    
            // 2. 将 maganize 里面的元素存到数组中
            for(int i = 0;i < magazine.length();i++) {
        
                ans[magazine.charAt(i) - 'a']++;
            }
    
            // 3. 遍历 ransomNote 里面的元素
            // 如果 ans 数组中有的话,就--
            for(int i = 0;i < ransomNote.length();i++) {
        
                ans[ransomNote.charAt(i) - 'a']--;
            }
    
            // 4. 遍历 ransomNote 每个字符
            // 判断 ans 对应元素是否 < 0
            // 比如:ransomNote = "a", magazine = "b"
            // a 字母对应下标的元素此时是 -1,就组成不了
            for(int i = 0;i < ransomNote.length();i++) {
        
                if(ans[ransomNote.charAt(i) - 'a'] < 0) {
        
                    return false;
                }
            }
    
            // 每个字母都没问题,那就返回 true,真的就没问题了
            return true;
        }
    }

## 三 . LeetCode 15 . 三数之和 ##

题目链接 : [15. 三数之和][15.]  
这道题 , 也是一道比较恶心的题 , 需要考虑的处理特别多  
同样 , 这道题还是可以使用哈希表 , 但是不推荐 , 给大家分享一下思路  
两层 for 循环 , 计算 a + b 的值 , 然后放进哈希表中 , 接下来再遍历一遍数组 , 去找哈希表中有没有 -(a+b) , 有的话将这三个元素放到答案数组中  
但是哈希表这个思路要处理的问题非常麻烦  
给大家介绍一个三指针思路 (实际上就是双指针)  
![image.png][image.png 2]  
如果大家还不懂的话 , 可以跳转到这里查看视频讲解  
[https://www.bilibili.com/video/BV1GW4y127qo/?spm\_id\_from=pageDriver&vd\_source=b0e82af8eb60883fa2180dda1770795d][https_www.bilibili.com_video_BV1GW4y127qo_spm_id_from_pageDriver_vd_source_b0e82af8eb60883fa2180dda1770795d]  
那代码也给大家贴到这里了

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            // 1. 定义答案链表
            List<List<Integer>> ans = new ArrayList<>();
            // 2. 先对数组进行排序!
            Arrays.sort(nums);
            // 3. 遍历数组每个元素
            for(int i = 0;i < nums.length;i++) {
        
                // 4. 数组已经从小到大排好序了,如果第一个数就是正数,那肯定找不到三个数相加 =0 的情况了
                // 直接就返回 ans 即可(剪枝操作)
                // 注意:不能返回 null
                // 比如:[-1,0,1,2,-1,-4]
                if(nums[i] > 0) {
        
                    return ans;
                }
    
                // 5. 对 a 进行去重
                // 注意:判断条件不能是nums[i] == nums[i+1]
                // 比如:[-1,-1,1],这样的话就会把第一个-1跳过去
                // 所以要写成 nums[i-1] == nums[i]
                if(i > 0 && nums[i-1] == nums[i]) {
        
                    continue;// 跳过本次循环
                }
    
                // 6. 定义左右指针
                // 左指针指向当前元素的下一个
                int left = i + 1;
                // 右指针指向数组最后一个元素
                int right = nums.length - 1;
                // 7. 第一个指针定在那里了,移动左右指针,找到符合条件的值
                // 循环条件不能取等,取等的话left right 相遇,就变成了两个元素了,题目要求返回三个元素
                while(left < right) {
        
                    // 将 a b c 三个值相加
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum > 0) {
         // 如果当前的和大,那就让右边变小一点
                        right--;
                    } else if (sum < 0) {
         // 如果当前的和小,那就让左边变大一点
                        left++;
                    } else {
        
                        // 找到 sum = 0 的情况了
                        // 先制作一个小链表
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        // 将小链表加入到答案链表中
                        ans.add(tmp);
                        // 继续去重
                        while(left < right && nums[left] == nums[left+1]) {
        
                            left++;
                        } 
                        while(left < right && nums[right] == nums[right-1]) {
        
                            right--;
                        }
                        left++;
                        right--;    
                    }
    
                }
            }
            return ans;
        }
    }

## 四 . LeetCode 18 . 四数之和 ##

题目链接 : [18. 四数之和][18.]  
![image.png][image.png 3]  
实际上 , 四数之和就是在三数之和基础上多增加了一层循环 , 其处理思想都是一样的  
还是需要进行剪枝操作和去重操作  
![image.png][image.png 4]  
那大家还是不理解的话 , 可以看视频讲解  
[https://www.bilibili.com/video/BV1DS4y147US/?spm\_id\_from=333.788&vd\_source=b0e82af8eb60883fa2180dda1770795d][https_www.bilibili.com_video_BV1DS4y147US_spm_id_from_333.788_vd_source_b0e82af8eb60883fa2180dda1770795d]

class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            // 1. 定义答案数组
            List<List<Integer>> ans = new ArrayList<>();
            // 2. 先对测试用例排序
            Arrays.sort(nums);
            // 3. 先定位到第一个指针的位置
            for(int k = 0;k < nums.length;k++) {
        
                // 4. 针对第一个指针进行剪枝
                // 注意:这次的剪枝操作必须确保第一个值 > target 以及 第一个值大于 0
                // 比如: -4 -1 0 0 , target=-5
                // -4+(-1)+0+0=-5 -> 等于 target
                // 直接剪枝就错过了这个结果集了
                if(nums[k] > target && nums[k] > 0) {
        
                    break;
                }
    
                // 5. 去重
                // 逻辑还是与三数之和一直,要与前面的数字进行判断
                if(k > 0 && nums[k] == nums[k - 1]) {
        
                    continue;
                }
    
                // 6. 定位到第二个指针,紧接在第一个指针后面
                // 此时第一个指针和第二个指针就变成了一个整体
                for(int i = k + 1;i < nums.length;i++) {
        
                    // 7. 针对第二个指针剪枝
                    // 注意:此时 nums[k] + nums[i] 是一个整体了
                    if(nums[k] + nums[i] > target && nums[k] + nums[i] > 0) {
        
                        break;
                    }
                    // 8. 去重
                    if(i > k + 1 && nums[i] == nums[i - 1]) {
        
                        continue;
                    }
    
                    // 9. 定位左右指针
                    int left = i + 1;
                    int right = nums.length - 1;
                    while(left < right) {
        
                        // 10. 计算四个指针相加的和,判断与 target 的关系
                        int sum =  nums[k] + nums[i] + nums[left] + nums[right];
                        if(sum > target) {
         // 大了就让右边往左挪一点
                            right--;
                        } else if (sum < target) {
         // 小了就让左边往右挪一点
                            left++;
                        } else {
         // 相等就将答案添加到答案集中
                            List<Integer> tmp = new ArrayList<>();
                            tmp.add(nums[k]);
                            tmp.add(nums[i]);
                            tmp.add(nums[left]);
                            tmp.add(nums[right]);
                            ans.add(tmp);
                            // 11. 不要忘记判断一下left right是否有重复的情况
                            while(left < right && nums[left] == nums[left + 1]) {
        
                                left++;
                            }
                            while(left < right && nums[right] == nums[right - 1]) {
        
                                right--;
                            }
                            // 12. left right 正常移动
                            left++;
                            right--;
                        }
                    }
                }
            }
            return ans;
        }
    }

今天的四道题还是有一点难度的 , 大家坚持住~  
如果对你有收获的话 , 请一键三连嗷~  
![image.png][image.png 5]

[https_programmercarl.com_other_xunlianying.html]: https://programmercarl.com/other/xunlianying.html
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e8e11fdf0cc1420db6c875e95aaaf4f1.png
[https_blog.csdn.net_m0_53117341_category_12247938.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/m0_53117341/category_12247938.html?spm=1001.2014.3001.5482
[http_t.csdn.cn_XkRlf]: http://t.csdn.cn/XkRlf
[454. _ II]: https://leetcode.cn/problems/4sum-ii/
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/737b205f9a6145788bc56f5ef2f51c4b.png
[383.]: https://leetcode.cn/problems/ransom-note/
[15.]: https://leetcode.cn/problems/3sum/
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/74f36278dd0f4cc28d9edb248090a582.png
[https_www.bilibili.com_video_BV1GW4y127qo_spm_id_from_pageDriver_vd_source_b0e82af8eb60883fa2180dda1770795d]: https://www.bilibili.com/video/BV1GW4y127qo/?spm_id_from=pageDriver&vd_source=b0e82af8eb60883fa2180dda1770795d
[18.]: https://leetcode.cn/problems/4sum/
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a23064ff577a43dda08fc6da94d4f10e.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/0c6e95af63c748c7bb5d4f2f7244b754.png
[https_www.bilibili.com_video_BV1DS4y147US_spm_id_from_333.788_vd_source_b0e82af8eb60883fa2180dda1770795d]: https://www.bilibili.com/video/BV1DS4y147US/?spm_id_from=333.788&vd_source=b0e82af8eb60883fa2180dda1770795d
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/71877a1ce5be4d62b122aa99d7499622.png