首页 > 其他分享 >两数之和到哈希表

两数之和到哈希表

时间:2024-10-31 11:16:29浏览次数:6  
标签:target nums int pattern arr2 哈希 两数

两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

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

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

  看到题目第一眼,暴力枚举,两个for循环解决。

class Solution {
    public int[] twoSum(int[] nums, int target) {
         int[] arr = new int[2];
         for(int i = 0;i < nums.length;i++){
             for(int j = i+1 ;j <= nums.length - 1;j++){
                 if(nums[i] + nums[j] == target){
                     arr[0] = i;
                     arr[1] = j;
                 }
             }
         }
         return arr;
    }

}

                                            

有没有更简单的方法。

哈希表

    哈希表,又称为散列表,是一种基于哈希函数组织数据的数据结构。它允许我们根据键值快速查找、插入和删除对应的值。哈希表的核心思想是通过哈希函数,将键值映射到一个固定大小的数组中的某个位置。

    在理想情况下,哈希表的查找、插入和删除操作都可以在常数时间内完成。如果可以结合哈希表正则可以大大缩短查找时间。

将已经遍历的数存入哈希表中,利用哈希表查找速度快的特点,查找当前的数的补数是否存在于哈希表中,如果存在则将下标存入数组即可。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sum = new int[2];
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(target-nums[i])){
                sum[0] = i;
                sum[1] = map.get(target-nums[i]);
                break;
            }
            map.put(nums[i],i);
        }
        return sum;
    }

}

                                           

同样还有一题也可以用到哈希表。

单词规律

给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern ="abba", s ="dog cat cat dog"

输出: true

示例 2:

输入:pattern ="abba", s ="dog cat cat fish"

输出: false

示例 3:

输入: pattern ="aaaa", s ="dog cat cat dog"

输出: false

使用两个哈希表 map1 和 map2 来建立字符到单词和单词到字符的双向映射。

  • map1 用于存储字符到单词的映射。

  • map2 用于存储单词到字符的映射

 

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] arr2 = s.split(" ");    
        if(arr2.length != pattern.length()){
            return false;
        }
        Map<Character,String> map1 = new HashMap<Character,String>();
        Map<String,Character> map2 = new HashMap<String,Character>();
        for(int i = 0 ;i < arr2.length;i++){
            if(map1.containsKey(pattern.charAt(i))){
                if(!map1.get(pattern.charAt(i)).equals(arr2[i])){
                    return false;
                }
            }
            if(map2.containsKey(arr2[i])){
                if(!map2.get(arr2[i]).equals(pattern.charAt(i))){
                    return false;
                }
            }
            map1.put(pattern.charAt(i),arr2[i]);
            map2.put(arr2[i],pattern.charAt(i));
        }
        return true;
    }
}

标签:target,nums,int,pattern,arr2,哈希,两数
From: https://blog.csdn.net/m0_74386799/article/details/143308708

相关文章

  • 代码随想录算法训练营第六天| leetcode242.有效的字母异位词、leetcode349.两个数组的
    1.leetcode242.有效的字母异位词题目链接:242.有效的字母异位词-力扣(LeetCode)文章链接:代码随想录视频链接:学透哈希表,数组使用有技巧!Leetcode:242.有效的字母异位词哔哩哔哩bilibili自己的思路:首先就是对字符串进行分开成一个一个单独的字母,然后使用列表存储这些数据,再对......
  • 【LeetCode】两数之和、大数相加
    主页:HABUO......
  • 必学算法——哈希算法
    目录前言一、什么是哈希算法二、哈希算法的原理三、哈希算法的特点四、哈希算法的应用场景五、经典例题1.字符统计代码题解[2.字符串统计](https://www.lanqiao.cn/problems/1206/learning/?page=1&first_category_id=1&name=%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BB%9F%E8%......
  • 0x02 Leetcode Hot100 哈希
    前置知识掌握每种语言的基本数据类型及其时间复杂度。Python:list、tuple、set、dictC++:STL中的vector、set、mapJava:集合类中的List、Set、Map为什么是哈希?在不同语言中,对于字典(dict)类的数据都会先将其键(key)进行哈希(Hash)运算,这个Hash值决定了键值对在内存中的存储位置,因此......
  • 【论文分享】HashGAT-VCA:一种结合哈希函数和图注意力网络的矢量元胞自动机模型,用于城
    本文考虑地块内部异质性,提出一个结合哈希函数和图注意力网络(GAT)的矢量元胞自动机(VCA)方法,用于研究城市土地利用变化;并将该模型应用于模拟深圳市2009年至2012年的城市土地利用变化,结果表明,HashGAT-VCA模型的模拟准确性显著优于其他VCA模型。【论文题目】HashGAT-VCA:Avecto......
  • 2.哈希函数
    哈希函数目标:极快且稳定特点:确定性/幂等性:对于相同的输入,哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠的。效率高:计算哈希值的过程应该足够快,哈希表的实用性越高。均匀分布:哈希算法应使得键值对均匀分布在哈希表中。分布越均匀,哈希冲突的概率就越低......
  • 散列表:哈希表的装载因子对散列冲突有什么影响?
    散列表:哈希表的装载因子对散列冲突有什么影响?哈希表的装载因子对散列冲突有着重要的影响。一、装载因子的定义装载因子是哈希表中已存储的元素个数与哈希表大小的比值。例如,如果一个哈希表中有10个元素,哈希表的大小为20,那么装载因子就是10/20=0.5。二、对散列冲突......
  • P3370 【模板】字符串哈希
    【模板】字符串哈希题目描述如题,给定NNN个字符串(第iii个字符......
  • 7、哈希表
    7、哈希表哈希表最主要的作用就是把一个比较庞大的空间或者值域映射到比较小的值域(0-n)就是将-10^9~10^9映射到0~10^5一、存储结构映射的方法可以是h(x)=xmod10^5但是这样映射会出现一个问题可能会有重复的数字出现所以就引出了两个方法开放寻址法和......
  • 「哈希表」是什么,有哪些常用的解决冲突的方法
    哈希表(HashTable),也被称为散列表,是一种数据结构,用于实现关联数组(AssociativeArray)或映射(Map)这样的抽象数据类型。常用的解决哈希表冲突的方法:1.链地址法(SeparateChAIning);2.开放寻址法(OpenAddressing);3.线性探查(LinearProbing)等。一、哈希表是什么哈希表(HashTable),也被称......