Leetcoder Day6 | 哈希表part02及总结

发布时间:2024年01月03日

语言:Java/C++?

目录

383. 赎金信

第15题. 三数之和

哈希法

双指针

第18题. 四数之和

今日总结


给你四个整数数组?nums1nums2nums3?和?nums4?,数组长度都是?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

?提示:

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

本题涉及四个独立的数组,只要找到A[i] + B[j] + C[k] + D[l] = 0就可以,不需要去重。本题符合判断某元素是否存在于数组中,所以优先考虑哈希法。接下来需要思考,用哈希法的什么数据结构来解题。本题可以看到数组中的元素范围较大,用数组下标进行映射会很稀疏浪费空间,因此考虑用set或map。在本题中,我们不仅需要判断数组之和,还要统计次数,涉及到两个值,因此用map结构会更合理。

因为是四个数组:

  • 如果将一个数组放入map中计算剩下的三个数组之和,时间复杂度是O(n)+O(n^3),得到 O(n^3);
  • 如果存两个数组之和,如AB。然后计算两个数组之和,如 CD。时间复杂度为O(n^2)+O(n^2),得到 O(n^2);
  • 如果存三个数组之和,如 ABC。然后计算一个数组,如 D。时间复杂度为:O(n^3)+O(n),得到 O(n^3);

因此综合来看,存放两个数组到map中时间复杂度最低。其实这就变成了在map中存储(a+b),判断另一个值0-(c+b)是否在map中出现过,跟1.两数之和很类似。


383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意:

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

这道题实际上是242.有效的字母异位词的更改版,有效字母异位词要求两个字符串能够互相组成,这里要求的是ransom能够由magazine组成即可。

按照题设,每个杂志里的字母不可重复使用。注意到这里只包含小写字母,所以可首选哈希法(用空间换时间),同样定义一个数组record,用来记录字符串magazine里字符出现的次数。字符a到字符z的ASCII是26个连续的数值,然后去判断ransom里的字母是否都存在于magazine中。因为这里元素是有限的考虑用数组来解决。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] record=new int[26];
        if(ransomNote.length()>magazine.length()){
            return false;
        }
        for(int i=0; i<magazine.length();i++){
            record[magazine.charAt(i)-'a']++;
        }
        for(int i=0;i<ransomNote.length();i++){
            record[ransomNote.charAt(i)-'a']--;
        }
        for(int count:record){
            if(count<0){
                return false;
            }
        }
        return true;

    }
}

这里可以看到跟有效字母异位词的区别就是,如果碰到count<0才是无效的,因为不要求magazine的所有字符都出现在ransom中,因此可以有多余的字母。


第15题. 三数之和

给你一个包含 n 个整数的数组?nums,判断?nums?中是否存在三个元素 a,b,c ,使得?a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

哈希法

这道题乍一看和之前做过的四数相加有点像,将a+b存入map中,然后判断来确定 0-(a+b) 是否在数组里出现过。但是有一个很明显的不同就是,这里要求不重复的三元组。所以本题的难点在于如何去除重复解。哈希法在查找的时候是没有顺序的,因此需要把符合条件的三元组放进vector中,然后再去重,过程较麻烦。

先对整个数组进行排序,然后按顺序遍历,第一个数值判断是否有重复值,因为有序,判断是否和下一个数重复即可。对a去重后,判断第二个元素b,同样方法去重,设置一个集合set,若c即-(a+b)存在于set中,则将当前a,b,c返回;若不存在,存储于set中,后移查找满足条件的c,直到数组结束。

import java.util.Set;
import java.util.HashSet;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);  //对数组中的元素进行排序。此时为升序
        
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                break;  // 排序后第一个元素都大于0,所有元素之和必不为0
            }
            if(i>0 && nums[i]==nums[i-1]){// 注意这里如果是 nums[i]==nums[i+1]可能会越界
                continue;  //三元组中的a去重
            }
            Set<Integer> set=new HashSet<>();  //确定第一个元素后对第二个去重
            for(int j=i+1;j<nums.length;j++){
                if(j>j+2 && nums[j-1]==nums[j-2]&& nums[j]==nums[j-1]){
                    continue; //对元素b去重
                }
                int c=-(nums[i]+nums[j]);
                if(set.contains(c)){//set中有满足的条件c,说明找到了符合条件的组合
                    result.add(List.of(nums[i],nums[j],c));
                    set.remove(c);  //把和c重复的值去掉   
                }
                else{
                    set.add(nums[j]);  //若没有找到c,则将当前第二个元素加入,向后移动
                }

            }
        }
    return result;
    }
}

双指针

可以看到哈希法在去重的操作中有很多细节需要注意。而且有两层for循环,因此还可以考虑使用双指针法,会更高效一些。

依旧先将数组排序,从数组开头进行遍历,设i为a所在的位置,设置left和right双指针,left指向i+1代表b所在的位置,right指向nums.length-1代表c所在位置。

因为是排序后的数组,所以我们会有一套规则:

  • 如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了,所以right下标就应该向左移动,这样才能让三数之和小一些。
  • 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。
??题目里强调的是不能有重复的三元组,但是三元组内的元素可以是重复的,因此需要判断nums[i]==nums[i-1]而不是nums[i]==nums[i+1],因为i+1此时指向的是left。
import java.util.Set;
import java.util.HashSet;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);  //对数组中的元素进行排序。此时为升序
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                return result;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]==0){
                    result.add(List.of(nums[i], nums[left], nums[right]));
                    while(right>left && nums[right]==nums[right-1]) right--;
                    while(right>left && nums[left]==nums[left+1]) left++;
                    right--;   //不要忘记移动left和right
                    left++;
                }
                else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return result;
        
    }
}

第18题. 四数之和

题意:给定一个包含?n 个整数的数组?nums?和一个目标值?target,判断?nums?中是否存在四个元素 a,b,c?和 d?,使得?a + b + c + d?的值与?target?相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例: 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。 满足要求的四元组集合为: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]?

?这里跟三数之和有同样的要求,不可以有重复的元素,因此依然可以采取双指针解法,区别在于四数之和为target而不是固定的0。这里要注意,在和固定为0的时候我们可以先判断nums[i] 是否大于0来筛选出一些条件,但是对于target不可以直接进行这样的剪枝,因为target也有为负数的情况。所以在第一步进行剪枝的时候,我们首先需要加上一些判断条件:设置k指向第一个元素,然后进行剪枝:nums[i]>target且nums[i]>=0时,才返回初始的result,否则需要一步步进行判断。随后设置j指向第二个元素,再一次进行剪枝,随后就和三数之和的思路一样了。

import java.util.Set;
import java.util.HashSet;

class Solution {
    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++){
            if(nums[i]>target && nums[i]>=0){
                break;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.length;j++){
                int sumAB=nums[i]+nums[j];
                if(sumAB>target && sumAB>=0){
                    break;
                }
                if(j>i+1 && nums[j]==nums[j-1]) {
                    continue;
                }
                int left=j+1;
                int right=nums.length-1;
                while(left<right){
                    int sumAll=sumAB+nums[left]+nums[right];
                    if(sumAll==target){
                        result.add(List.of(nums[i], nums[j], nums[left],nums[right])); 
                        while(right>left && nums[right]==nums[right-1]) right--;
                        while(right>left && nums[left]==nums[left+1]) left++;
                        right--;
                        left++;
                    }
                    else if(sumAll>target){
                        right--;
                    }
                    else{
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

?? 我一开始在if(nums[i]>target && nums[i]>=0)if(sumAB>target && sumAB>=0) 满足条件时 return result;,结果报错了

原因是如果使用 return result;,代码会直接返回 result 并结束函数,导致后续的迭代无法执行,从而遗漏了可能存在的其他符合条件的四元组。

今日总结

今天遇到了三种n数之和的问题,在做题时一定要看好条件,如果不要求含不重复的元组,使用哈希法会很方便;若对元素有要求,尤其是要求不重复时,使用哈希便会很麻烦,可以考虑双指针来解决。

文章来源:https://blog.csdn.net/weixin_36675391/article/details/135348702
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。