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

解题思路

S1: 暴力枚举 O(n2)

思路及算法：依次遍历数组中每一个数x，寻找数组中是否存在 target - x。
注意：避免元素重复比较，所以我们只需要在 x 后面的元素中寻找 target - x。

  1. class Solution {
  2.     // 思路：1.按顺序比较两数之和，命中则返回下标
  3.     // 2.注意两数相加越界场景，解决方案：用目标数 - 其中一个数
  4.     public int[] twoSum(int[] nums, int target) {
  5.         int n = nums.length;
  6.         for (int i = 0; i < n; i++) {
  7.             // int j=i+1,仅比较i后面的元素
  8.             for (int j = i + 1; j < n; j++) {
  9.                 if (nums[i] + nums[j] == target) {
  10.                     return new int[]{i, j};
  11.                 }
  12.             }
  13.         }
  14.         return new int[0];
  15.     }
  16. }

S2: 哈希表-空间换时间 O(n)

我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

思路及算法：这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中(key=x=nums[i] , value=i ), 即可保证不会让 x 和自己匹配。

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
  4.         for (int i = 0; i < nums.length; ++i) {
  5.             // 缓存已遍历的数值和下标，便于后续元素快速比较匹配
  6.             if (hashtable.containsKey(target - nums[i])) {
  7.                 return new int[]{hashtable.get(target - nums[i]), i};
  8.             }
  9.             hashtable.put(nums[i], i);
  10.         }
  11.         return new int[0];
  12.     }
  13. }