首页 > 其他分享 >Day6 (哈希表)| 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

Day6 (哈希表)| 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

时间:2024-07-10 21:19:58浏览次数:20  
标签:四数 15 nums Day6 示例 三元组 int right left

454.四数相加II

给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

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

示例 1:

输入: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

示例 2:

输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1

代码如下:

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

383.赎金信

给你两个字符串:ransomNotemagazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以,返回 true ;否则返回 false

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

示例 1:

输入:ransomNote = "a", magazine = "b"
输出:false

示例 2:

输入:ransomNote = "aa", magazine = "ab"
输出:false

示例 3:

输入:ransomNote = "aa", magazine = "aab"
输出:true

此题和242.有效的字母异位词很相似,不再写思路了

代码如下:

 public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数,说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }

15.三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

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

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

示例 1:

输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

这题没时间写了,思路看懂了但是还需要自己琢磨,码上

代码如下:

 List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后,对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;

18.四数之和

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

  • 0 <= a, b, c, d < n
  • abcd 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

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

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

这两题后续会重新做一遍

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {

            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

标签:四数,15,nums,Day6,示例,三元组,int,right,left
From: https://www.cnblogs.com/flydandelion/p/18295023

相关文章

  • The 1st Universal Cup. Stage 15: Hangzhou
    Preface久违的线下训练,结果因为祁神有急事赶回家了就我和徐神两个人打开场就感觉有点不对劲怎么没有签到,然后全程对着几个题红温还想了一堆假算法,最后愉悦暴毙感觉这场题本身质量都挺高的,但最后只写了5个(赛后补了一个),等以后有时间再来补补吧A.TurnontheLight徐神开场一......
  • HAJX[2024] 15Day游记
    洛谷食用博客食用简介:这是一个正在学习C++的OIer(很蒻很蒻)的日常记录。(注:2024.7.5-7.20集训日更)放在前面:本贴只是记录一下本蒟蒻的生活,(太菜了),佬们轻喷谢谢~浏览次数:(由于网站原因可能无法显示,属于正常现象)Day0期待集训ing。0-上午在来的路上听歌(摆。中午到了JZYZ......
  • 【基于R语言群体遗传学】-15-溯祖理论coalescence
    在群体遗传学中,一个非常重要的概念是关注谱系的汇聚(遗传线索的汇合),当我们回溯过去几代人口时。在之前的博客中,我们几乎只处理了随时间推移基因变化的“正向”模拟。群体遗传学_tRNA做科研的博客-CSDN博客然而,通过时间逆向建模等位基因频率变化不仅是一个有趣的视角,当你知道......
  • 1575 二叉苹果树
    //1575:【例1】二叉苹果树.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://ybt.ssoier.cn:8088/problem_show.php?pid=1575https://loj.ac/p/10153有一棵二叉苹果树,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵树共N个节点,标号......
  • 内存管理-15-Arm64汇编
    1.Arm64汇编lsr指令LSR是ARM架构的位移动指令,用于逻辑右移操作。它将第一个操作数的位向右移动指定位数,并根据需要将符号位(在有符号数操作中)扩展到空出来的位。语法:LSR{条件}{S}移位量,寄存器条件是可选的,指定为如EQ、NE等,用来指明只有在特定条件下才能执行指令。S是可......
  • 关于力扣150题目——逆波兰表达式求值Java实现的三种解法
    题目介绍逆波兰表达式是一种后缀表达式,其运算符位于操作数之后。力扣150题目要求我们实现一个函数,计算给定逆波兰表达式的值。本文将介绍三种不同的Java实现方法来解决这个问题。解法一:使用栈这是最直观和常见的解法,使用栈来存储操作数,并在遇到运算符时从栈中弹出操作数......
  • 代码随想录算法训练营第七天 | 454.四数相加
    1、四数相加不需要考虑去重四个数组采两个数组一起相加的遍历方式,为了缩短时间复杂度。classSolution{public:intfourSumCount(vector<int>&nums1,vector<int>&nums2,vector<int>&nums3,vector<int>&nums4){unordered_map<int,int>......
  • 15、 Django-多表操作-多个模块的关联-多对多的增删改查- models.manytomany()
    针对多对多的关系django会自动创建第三张表、也可以通过through参数指定第三张表 models.pyfromdjango.dbimportmodels#Createyourmodelshere.#多对多#用户表:电影=N:M#一个用户可以收藏多部电影#一部电影可以被不同的用户收藏#电影classMovie(models.M......
  • 代码随想录刷题day 7 | 哈希表part02 454.四数相加II 383. 赎金信 15. 三数之和
    454.四数相加II//这道题使用哈希就可解决,使用一个map存储前两个数组中,所有组合产生的sum的频率;对于后两个数组中所有的组合,每出现一个和的相反数出现在map中,则代表出现了这个相反数频率个组合可以满足四数相加为0classSolution{publicintfourSumCount(int[]nums1,......
  • Day65 代码随想录打卡|回溯算法篇---组合总和II
    题目(leecodeT40):给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用 一次 。注意:解集不能包含重复的组合。 方法:本题的要求是每个元素在组合中只能......