Two Sum

Question * Easy *

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.)

Hints：

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int result = 0;
        int[] resultArray = new int[2];
     try{
        for(int i=0; i < nums.length; i++){
            for(int j=i+1; j < nums.length; j++){
                 result = nums[i] + nums[j]; 
                 if(result == target){
                      resultArray[0] = i;
                      resultArray[1] = j;
                      return resultArray; 
                 }
            }
        } 
     }catch(Exception e){
         System.out.println("There is no solution");
     }
    return resultArray;
    }
}

我的想法是 通过遍历所提供的数组，如果可以找到两数相加等于目标数。这样就可以返回这两个数字的Index。然后把这两个数的Index 形成一个新的数组作为return。

但是我在看solution的时候，发现我的解题思路被归类为 Brute Force. solution里面还有其他方法 Two- pass Hash Table, One-Pass Hash Table. 我的解题方法被归类为Brute Force是因为 time complexity == O($n^2$) . 我的这种方法对于每一个元素，每一次loop数组剩下的元素查找它的补数需要花的时间是O(n)，所以两层for循环下来 time complexity == O($n^2$). 可见下图，我的方法不是优解，时间复杂度有点高。

TIME COMPLEXITY

​ 语句执行次数称为语句频度或时间频度,记为T(n)。 有了基本操作执行次数的函数T(n)也无法准确比较代码的运行时间。 比如算法A T(n) = 100n, 算法B T(n) = 5$n^2$,算法A和算法B谁的运行时间长就和n的取值有关了。因此有了渐进时间复杂度 (Asymptotic Time Complexity)的概念.

​ 若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作：T(n) = O(f(n))， 称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度，也称大O表示法。 时间复杂度决定了程序的运行效率，因此特别重要

时间复杂度原则：

  1. 如果运行时间 T(n)是常数量级，则 O(1) 表示。
  2. T(n) 只保留时间函数中的最高阶项。
  3. T(n) 可以省去最够阶项前面的系数。

这篇简书的文章写的很好：https://www.jianshu.com/p/f4cca5ce055a

这篇漫画解释时间复杂度及其重要性也写得很好：https://www.cxyxiaowu.com/5323.html

Two-pass Hash Table

利用hash table，将空间换为速度从而把查找时间降低。利用hash table几乎可以快速查找。“几乎”是因为冲突发生，查找时间还是会退化回去。 在Two-pass Hash Table里面会用到两次iterations.第一次是把每一个元素的value和index添加进table。第二次是查找元素的补数。

1
2
3
4
5
6
7
8
9
10
11
12
13
   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 solution");
}

这样的话，时间复杂度就是O(n)，显然没有嵌套的for循环。 每一次查询时间是O(1).

One-pass Hash Table

和 two-pass hash table 不同的就是， one-pass hash table可以 insert element into table 的时候 check 当前 元素的补数是否已经存在表格里了。如果存在 则返回solution。

1
2
3
4
5
6
7
8
9
10
11
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 solution");
}

时间复杂度也显然是O(n). 空间复杂度也是O(n)，额外的空间取决于有多少的items要存进hash table.

HashMap

创建对象——> HashMap<String,Integer> hashMap = new HashMap<>();

存储数据 通过put （key,value)——> hashMap.put("aa",1);

put方法会覆盖原有的value。另一种方法putIfAbsent(key,value) 不会覆盖。

​ hashMap.putIfAbsent("aa",4);

删除元素

remove(key):删除成功(存在key)，返回被删除的key对应的value，否则返回null。

remove(key,value):删除成功（存在entry），返回true，否则返回false。

​ hashMap.remove("aa",5);

获取元素

hashMap.get("aa");

getOrDefault在key不存在时,返回一个defaultValue。

​ getOrDefault("aa",-1);

元素遍历

1
2
3
4
5
Iterator iterator = hashMap.keySet().iterator();
while (iterator.hasNext()){
    String key = (String)iterator.next();
    System.out.println(key+"="+hashMap.get(key));
}

判断Key或者value是否存在

1
2
hashMap.containsKey("aa");
hashMap.containsValue(1);

替换元素

hashMap.replace("ff",5);