题目

https://leetcode-cn.com/problems/two-sum/

方法一、暴力枚举

思路

这道题作为力扣第一题，属于简单级别，最容易想到的就是暴力枚举，循环数组中的每一个数 x，然后再for循环寻找数组中是否存在 target - x。

代码

  1. public class Ex1 {
  3.     // 常规解法
  4.     // 时间复杂度O^2
  5.     // 空间复杂度O(1)
  6.     public static int[] twoSum(int[] nums, int target) {
  7.         for (int i = 0; i < nums.length; i++) {
  8.             for (int j = 1; j < nums.length; j++) {
  9.                 if (i == j) {
  10.                     continue;
  11.                 }
  12.                 if (nums[i] + nums[j] == target) {
  13.                     return new int[]{i, j};
  14.                 }
  15.             }
  16.         }
  17.         return null;
  18.     }
  19. }

复杂度分析

  • 时间复杂度：O(N^2)O(N_2)，其中 N_N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

  • 空间复杂度：O(1)。

    方法二、哈希表

    思路

    这个思路是我在评论区看到的，很有创意，思路是使用哈希表去维护补数，这样就省去了寻找 target - x的一层for循环，代价是空间复杂度由O(1)升到O(N)。

    代码

    public class Ex2 {

  // 解法二
  public static int[] twoSum(int[] nums, int target) {
      int[] result = new int[2];
      // key:补数 value:下标
      Map<Integer, Integer> hash = new HashMap<>(nums.length);
      for (int i = 0; i < nums.length; i++) {
          // 如果含有补数就代表满足条件
          if (hash.containsKey(nums[i])) {
              result[0] = hash.get(nums[i]);
              result[1] = i;
              return result;
          }
          hash.put(target - nums[i], i);
      }
      return result;
  }
}

    复杂度分析

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