链接：https://leetcode-cn.com/problems/two-sum/

解题思路：哈希表

我们可以使用哈希表这种数据结构。

算法流程：

  • 初始化哈希表
  • 遍历数组，判断元素 target-nums[i] 是否在哈希表中
    • 如果 target-nums[i] 不在哈希表中，我们就将 (nums[i],i) 添加到哈希表
    • 如果 target-nums[i] 在哈希表中，我们就将两个符合条件的下标以数组形式返回
  • 遍历 nums 后，仍然没有找到返回值，则抛出 IllegalArgumentException

代码

  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.             if(map.containsKey(target-nums[i])){
  6.                 return new int[]{map.get(target - nums[i]),i};
  7.             }
  8.             map.put(nums[i],i);
  9.         }
  10.         throw new IllegalArgumentException("Argument is illegal!");
  11.     }
  12. }

复杂度分析

  • 时间复杂度：

只遍历一次数组 nums，所以时间复杂度为

  • 空间复杂度：

因为我们额外使用了哈希表这种数据结构，所以额外空间复杂度为