题目链接

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

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

示例 2：

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

示例 3：

  1. 输入：nums = [3,3], target = 6
  2. 输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解法 1

思路：

  • 遍历 nums
    • 获取到 nums 中的每个元素 num，然后 minuend = target - num（minuend 是补数）
    • 判断 minuend 是否在 nums 中（再次遍历）
      • 如果在，则 return [index[num], index[minuend]]
      • 否则继续遍历

代码实现：

  1.     public int[] twoSum(int[] nums, int target) {
  2.         for (int i = 0; i < nums.length; i++) {
  3.             int minuend = target - nums[i];
  4.             int index = getIndex(nums, minuend, i + 1);
  5.             if (index >= 0) {
  6.                 return new int[]{i, index};
  7.             }
  8.         }
  9.         return null;
  10.     }
  12.     /**
  13.      *
  14.      * 查找 target 是否在 nums 中，如果在，则返回对应索引，否则返回 -1
  15.      *
  16.      * @param nums   nums
  17.      * @param target target
  18.      * @param startIndex 开始查找的位置
  19.      * @return index
  20.      */
  21.     private int getIndex(int[] nums, int target, int startIndex) {
  22.         for (int i = startIndex; i < nums.length; i++) {
  23.             if (nums[i] == target) {
  24.                 return i;
  25.             }
  26.         }
  27.         return -1;
  28.     }

执行结果：
image.png

复杂度分析

  • 时间复杂度：很明显是 O(n2)，其中 N 是数组中元素的数量，最坏情况下数组中任意两个数都要匹配一次
  • 空间复杂度：O(1)

解法 2

利用哈希表

思路：

  • 建立一个 hashmap

    minuend = target - num，minuend 是补数，target 是给出的数，num 是 nums 中的某个元素

  • 遍历 nums 获取到其中的每个元素 num

    • 查找 hashmap 中是否已经存在根据 num 构建出来的补数信息，如果有，则直接取出补数信息，加上当前遍历索引，直接返回结果
    • 否则根据当前的 num 构建补数信息，放入 hashmap 中

代码实现：

  1.     /**
  2.      *
  3.      * 利用哈希表
  4.      *
  5.      * @return 数组下标
  6.      */
  7.     public int[] twoSum(int[] nums, int target) {
  8.         HashMap<Integer, Integer> map = new HashMap<>();
  9.         for (int i = 0; i < nums.length; i++) {
  10.             // 查找 map 中是否存在根据当前元素构建出来的补数信息
  11.             if (map.containsKey(nums[i])) {
  12.                 return new int[]{map.get(nums[i]), i};
  13.             }
  14.             // 根据当前元素构建补数信息
  15.             map.put(target - nums[i], i);
  16.         }
  17.         return null;
  18.     }

执行结果：
image.png

复杂度分析

  • 时间复杂度：O(N)，其中 N 是数组中元素的数量，对于每个元素，我们可以 O(1) 的寻找 target - nums[i]
  • 空间复杂度：O(N)，其中 N 是数组中的元素数量，主要为哈希表的开销

反思

用 hashmap 存储所需要的信息，需要查找的信息存入到 key，比如此题 key 存储了一个余数信息反而不是索引 index