提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【算法】哈希表 ( 两数之和 )

算法哈希 两数
2023-06-13 09:17:54 时间

算法 系列博客

【算法】刷题范围建议 和 代码规范 【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串 ( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 ) 【算法】双指针算法 ( 有效回文串 II ) 【算法】哈希表 ( 两数之和 )

文章目录

使用哈希表解决问题 , 一般不需要手动实现哈希表 , 一般使用 HashSet 或 HashMap 即可 ;

一、两数之和

两数之和 : https://www.lintcode.com/problem/56/

给定一个未排序的数组 , 找到数组中的两个元素之和 , 等于给定的 target 值 ;

该问题最直观的解法 , 就是 蛮力算法 ;

如 : 给定数组 [6, 4, 2, 9] , 给定 target 值为 10 , 找出数组中哪两个元素之和为 10 ;

如果使用蛮力算法 , 就是遍历所有的数组元素 , 如 遍历 6 , target ( = 10 )减去该被遍历的元素 , 结果是 4 , 然后检测 4 在不在数组中 ; 这样需要设计 两层循环 , 外层循环遍历数组元素 , 内层循环遍历 target - 数组元素 值是否在数组中 ; 上述算法事件复杂度为

O(n^2)

;

这里的内层循环中 , 检测一个数字是否在数组中 , 可以使用 哈希表 进行实现 , 哈希表查询的单次操作的时间复杂度是

O(1)

,

n

次查询的操作是

O(n)

; 哈希表在该算法中 , 既不是输入 , 也不是输出 , 是算法计算过程中的耗费 , 因此其空间复杂度是

O(n)

;

哈希表的 时间复杂度是

O(n)

, 空间复杂度是

O(n)

;

哈希表存使用 HashMap 集合体现 ; 设计一个循环 , 遍历数组元素 number ; 遍历时检测 target - number 是否在HashMap中 , 如果不在 , 则加入到哈希表中 ;

将 target - number 的值作为 HashMap 集合的 Key 键 , 将该 number 的索引作为 Value 值 ;

上述操作 , 一边遍历 , 一边将数组元素插入到哈希表中 , [3, 6, 2, 4] , 在遍历到 6 时 , 从哈希表中查找 10 - 6 = 4 这个值 , 哈希表中没有 4 , 但此时将 4=2 键值对 插入了 HashMap , 在之后遍历 4 时 , 肯定能找到索引值 2 ;

按照这种遍历方式 , 如果存在这两个元素 , 总能在

O(n)

时间内找到两个值

代码示例 :

import java.util.HashMap;

class Solution {

    public int[] twoSum(int[] numbers, int target) {
        // 键存放 target - numbers[i], 值存放对应的 i 索引值
        // 如果正在遍历的 numbers[j], 恰好等于某个 target - numbers[i]
        // 说明 i, j 就是要找的两个索引值
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        // 要返回的值
        int[] result = new int[2];

        for (int i = 0; i < numbers.length; i++) {
            if (hashMap.get(numbers[i]) != null) {
                // 如果集合中有该值, 说明已经找到了两数之和为 target 的两个元素了, 可以直接返回
                result[0] = hashMap.get(numbers[i]);
                result[1] = i;
                return result;
            }
            // 向哈希表中存储 target - numbers[i]
            hashMap.put(target - numbers[i], i);
        }

        return result;
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println(
                new Solution().twoSum(new int[]{1,2,4,6}, 10)
        );
    }
}

相关文章