Leetcode 001 TwoSums

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Intuition:

首先明确题目需要我们做的是返回一个和所对应的两个加数在数组中的下标。直接两层遍历当然很容易，但是时间复杂度会达到O(n2),那么接下来我们就开始用空间换时间。

我们肯定要把整个数组进行一次遍历，那么在遍历的过程中我们只要能够找到和减去当前数组下标元素的差所对应在数组中的下标整个题目就完成了。

接下来的任务就是进行高效率的查找。自然而然就会想到查找时间复杂度为O(1)的hashmap.然后我们把数组中的所有元素放到Hashmap里面，key表示为数组中元素的值，这样遍历的时候一旦得到和与当前元素的差，直接用差作为hashmap的key进行查找即可直接返回数组下标。

Solution:

public static int[] twoSumSolution(int[] nums, int target) {
  	/*
       * We reduce the look up time from O(n)O(n) to O(1) by
       * trading space for speed. A hash table is built exactly
       * for this purpose, it supports fast look up in near constant time.
       * look up in hash table should be amortized O(1).
       */

      //节省时间的技巧是利用hashmap搜索复杂度为(1)的特点，用hashmap来搜素，而不是
      //手动遍历（O(n)）
      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];
          //&&map.get(complement)!=i也很关键，这样确保数组中的同一个元素不会被重复使用
          if (map.containsKey(complement) && map.get(complement) != i) {
              return new int[] { i, map.get(complement) };
          }
      }
      throw new IllegalArgumentException("No two sum solution");
  }