Hexo搭建个人博客

两数之和

---

题目：

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

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

示例:

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

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

---

解法一：暴力法

• 思路：通过遍历数组余下的值，是否等于target-x来判断是否有该值

  class Solution1 {
      public int[] twoSum(int[] nums, int target) {
          for (int i = 0; i < nums.length; i++) {
              for (int j = i + 1; j < nums.length; j++) {
                  if (nums[j] == target - nums[i]) {
                      return new int[] { i, j };
                  }
              }
          }
          throw new IllegalArgumentException("No two sum solution1");
      }
  }

• 时间复杂度：O(n^2)
  对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。

• 空间复杂度：O(1)

解法二：两遍哈希表法

• 思路：
  1、为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。
  2、实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元（target - nums[i]）是否存在于表中。注意，该目标元素不能nums[i] 本身！

  class Solution2 {
      public int[] twoSum(int[] nums, int target) {
          Map<Integer, Integer> map = new HashMap<>();
          for (int i = 0; i < nums.length; i++) {
              map.put(nums[i], i);
          }
          for (int i = 0; i < nums.length; i++) {
              int complement = target - nums[i];
              if (map.containsKey(complement) && map.get(complement) != i) {
                  return new int[] { i, map.get(complement) };
              }
          }
          throw new IllegalArgumentException("No two sum solution2");
      }
  }

• 时间复杂度：O(n)
  我们把包含有 n个元素的列表遍历两次。由于哈希表将查找时间缩短到O(1) ，所以时间复杂度为 O(n)。

• 空间复杂度：O(n)
  所需的额外空间取决于哈希表中存储的元素数量，该表中存储了n个元素。

解法三：一遍哈希表法

• 思路：由于可以在遍历数组的同时判断是否存在target-nums[i]，可以加一个判断。

  class Solution3 {
      public int[] twoSum(int[] nums, int target) {
          Map<Integer, Integer> map = new HashMap<>();
          for (int i = 0; i < nums.length; i++) {
              int complement = target - nums[i];
              if (map.containsKey(complement)) {
                  return new int[] { map.get(complement), i };
              }
              map.put(nums[i], i);
          }
          throw new IllegalArgumentException("No two sum solution3");
      }
  }

• 时间复杂度：O(n)
  我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

• 空间复杂度：O(n)
  所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

比较说明（个人观点）

• Map 本身会带来时间和空间上的开销，这无可否认。但我喜欢使用Map的方法，原因有二，（1）Map帮助解决了元素值和索引的映射，这个数据结构干这个很方便；（2）算法的设计以及优劣的判断还是依靠时间复杂度+空间复杂度，注意是复杂度，关注的更多的是时间和空间消耗随着问题规模的一个增长快慢程度，显然方法二、方法三比方法一要好很多。方法三比方法二更好，好在平均情况，找到一个结果，立马返回，而不必对每个元素都进行存储。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2113132982@qq.com