算法:两数之和。

妖狐艹你老母 2023-02-22 12:10 124阅读 0赞

题目描述

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法:一遍哈希表

事实证明,我们可以一次完成。在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。

  1. class Solution {
  2. public int[] twoSum(int[] nums, int target) {
  3. Map<Integer, Integer> map = new HashMap<>();
  4. for (int i = 0; i < nums.length; i++) {
  5. int complement = target - nums[i];
  6. if (map.containsKey(complement)) {
  7. return new int[] { map.get(complement), i };
  8. }
  9. map.put(nums[i], i);
  10. }
  11. throw new IllegalArgumentException("No two sum solution");
  12. }
  13. }

复杂度分析:

  • 时间复杂度:O(n),我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
  • 空间复杂度:O(n),所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 n 个元素。

发表评论

表情:
评论列表 (有 0 条评论,124人围观)

还没有评论,来说两句吧...

相关阅读

    相关 之和

    定一个整数数组 **`nums`**和一个目标值 **`target`**,请你在该数组中找出和为目标值的那 **两个** 整数,并返回他们的数组下标。 你可以假设每种...

    相关 之和

    两数之和 1、题目 > 题目要求 给定一个整数数组 `nums` 和一个目标值 `target`,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下

    相关 之和

    题目描述 给出一个整数数组,请在数组中找出两个加起来等于目标值的数, 你给出的函数twoSum 需要返回这两个数字的下标(index1,index2),需要满足 ind

    相关 之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能

    相关 之和

    题目: 给定一个整数数组 `nums` 和一个目标值 `target`,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应

    相关 之和

    > 题目: > 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 > 你可以假设每种输入只会

    相关 之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不

    相关 之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能