1. 两数之和

难度: 简单

来源: 每日一题 2023.07.01

---

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

只会存在一个有效答案

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
    }
}

分析与题解

---

• 暴力法(遍历寻找法)

  对于这个问题,我们可以直接使用利用两层遍历来寻找合适的答案, 整体方案比较暴力, 简单易懂, 就是效率有点不太高....

  所以整体的解题方案如下所示.

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          for (int i = 0; i < nums.length - 1; i++) {
              for (int j = i + 1; j < nums.length; j++) {
                  if (nums[i] + nums[j] == target) {
                      return new int[]{i, j};
                  }
              }
          }
          return new int[]{};
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n²), 因为是需要两层遍历。
  • 空间复杂度: O(1).

  结果如下所示.

  

• HashMap法

  其实这种解法对我这两年的实际开发过程中是影响深远的, 虽然<<大话数据结构>> 我在16年就读完了, 但是对时间复杂度和空间复杂度没有较深的认知, HashMap法让我深刻的理解了什么叫做 空间换时间 .

  回归整体,相比于暴力寻找法,我们只需要做两步事情.

  • 首先判断当前数组元素 target - nums[i] 是否存在于HashMap中.

  • 如果不存在, 则以 nums[i] 为key, i 为value存入HashMap中.

  • 如果存在, 则找到了唯一的答案, 返回 [i , cache.get(target - nums[i])] 即可完成解题.

  class Solution {
      public int[] twoSum(int[] nums, int target) {
          Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
          for (int i = 0; i < nums.length; i++) {
              if (cache.get(target - nums[i]) != null) {
                  return new int[]{cache.get(target - nums[i]), i};
              } else {
                  cache.put(nums[i], i);
              }
          }
          return new int[]{};
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 其中 n 为 nums 的长度。
  • 空间复杂度: O(n), 只需要开辟一个内存容量为 nums 长度的 HashMap即可.

  结果如下所示.