• 哈希表题目:两数之和


    题目

    标题和出处

    标题:两数之和

    出处:1. 两数之和

    难度

    2 级

    题目描述

    要求

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

    你可以假设每种输入恰好有一个答案,不能重复使用数组中同一个元素。

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

    示例

    示例 1:

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

    示例 2:

    输入: nums   =   [3,2,4],   target   =   6 \texttt{nums = [3,2,4], target = 6} nums = [3,2,4], target = 6
    输出: [1,2] \texttt{[1,2]} [1,2]

    示例 3:

    输入: nums   =   [3,3],   target   =   6 \texttt{nums = [3,3], target = 6} nums = [3,3], target = 6
    输出: [0,1] \texttt{[0,1]} [0,1]

    数据范围

    • 2 ≤ nums.length ≤ 10 4 \texttt{2} \le \texttt{nums.length} \le \texttt{10}^\texttt{4} 2nums.length104
    • -10 9 ≤ nums[i] ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9} -109nums[i]109
    • -10 9 ≤ target ≤ 10 9 \texttt{-10}^\texttt{9} \le \texttt{target} \le \texttt{10}^\texttt{9} -109target109
    • 只会存在一个有效答案

    进阶

    你可以想出一个时间复杂度小于 O(n 2 ) \texttt{O(n}^\texttt{2}\texttt{)} O(n2) 的算法吗?

    解法一

    思路和算法

    假设数组 nums \textit{nums} nums 的长度是 n n n,则需要找到两个下标 i i i j j j,满足 0 ≤ i < j < n 0 \le i < j < n 0i<j<n nums [ i ] + nums [ j ] = target \textit{nums}[i] + \textit{nums}[j] = \textit{target} nums[i]+nums[j]=target

    最简单的做法是使用两层循环遍历,外层循环在范围 [ 0 , n − 1 ] [0, n - 1] [0,n1] 中遍历下标 i i i,内层循环在范围 [ i + 1 , n − 1 ] [i + 1, n - 1] [i+1,n1] 中遍历下标 j j j,当遇到一对下标 ( i , j ) (i, j) (i,j) 满足 nums [ i ] + nums [ j ] = target \textit{nums}[i] + \textit{nums}[j] = \textit{target} nums[i]+nums[j]=target 时,返回下标 i i i j j j 即可。

    代码

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    if (nums[i] + nums[j] == target) {
                        return new int[]{i, j};
                    }
                }
            }
            return new int[]{-1, -1};
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    复杂度分析

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要使用两层循环遍历数组 nums \textit{nums} nums

    • 空间复杂度 O ( 1 ) O(1) O(1)

    解法二

    思路和算法

    解法一中,相同的下标被重复计算了多次,因此时间复杂度较高。如果使用哈希表存储已经遍历过的元素与下标,可以将时间复杂度降低到 O ( n ) O(n) O(n)

    哈希表的键为已经遍历过的元素,值为元素所在下标。

    当遍历到下标 i i i 时,令 num = nums [ i ] \textit{num} = \textit{nums}[i] num=nums[i],如果哈希表中存在元素 target − num \textit{target} - \textit{num} targetnum 作为哈希表的键,则可以根据哈希表得到元素 target − num \textit{target} - \textit{num} targetnum 所在下标 prevIndex \textit{prevIndex} prevIndex,此时 ( prevIndex , i ) (\textit{prevIndex}, i) (prevIndex,i) 即为答案。由于使用哈希表查找,因此对于每个元素 num \textit{num} num 都可以在 O ( 1 ) O(1) O(1) 的时间内判断 target − num \textit{target} - \textit{num} targetnum 是否在哈希表中,总时间复杂度为 O ( n ) O(n) O(n)

    由于题目要求不能重复使用数组中同一个元素,因此对于每个元素 num \textit{num} num,应该首先判断哈希表中是否存在元素 target − num \textit{target} - \textit{num} targetnum,然后将 num \textit{num} num 加入哈希表。如果哈希表中存在元素 target − num \textit{target} - \textit{num} targetnum,则该元素的下标一定小于当前下标,因此 target − num \textit{target} - \textit{num} targetnum 所在下标与 num \textit{num} num 所在下标一定不同(即使 target − num \textit{target} - \textit{num} targetnum 的值与 num \textit{num} num 的值相等,如示例 3)。

    代码

    class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                int num = nums[i];
                if (map.containsKey(target - num)) {
                    int prevIndex = map.get(target - num);
                    return new int[]{prevIndex, i};
                }
                map.put(num, i);
            }
            return new int[]{-1, -1};
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    复杂度分析

    • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 一次,对于每个元素都可以在 O ( 1 ) O(1) O(1) 的时间内完成对哈希表的操作,因此总时间复杂度是 O ( n ) O(n) O(n)

    • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要使用哈希表存储遍历过的数字,哈希表的元素个数不会超过 n n n

  • 相关阅读:
    跑在笔记本里的大语言模型 - GPT4All
    基于android的个性闹铃的设计与开发(闹铃,日历,计时器,备忘录)
    SpringBoot 整合 Minio 上传文件
    【MySQL】深入理解MySQL索引优化器工作原理
    微软发现影响 Linux 和 macOS系统的 ncurses 库漏洞
    【数据结构初阶】算法的时间复杂度和空间复杂度
    渗透测试-靶机打靶思路与方法
    openGL第一个程序
    Web攻防01-ASP应用相关漏洞-HTTP.SYS&IIS短文件&文件解析&ACCESS注入
    利用SoapUI工具生成Java WebService客户端代码
  • 原文地址:https://blog.csdn.net/stormsunshine/article/details/121451359