【LeetCode Easy】001 Two Sum

Easy 001 Two Sum

Description:

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

My Solution:

  1. 两个for循环嵌套暴力计算

    • 时间复杂度达到了O(n²)
  2. 两个指针首尾并行

    • 时间复杂度O(n)
    • 这种方法可以满足这道题的要求,因为题目中明确说明了each input has exactly one solution,但是当答案不止一个时,如input为[2,2,7,11,15]时,就不能用这种方法了

Fast Solution:

  1. 用到HashMap

    • for循环遍历数组,对每个元素计算和target的差,如果该差在map中,返回两个位置,如果该差不在map中,则将该元素及其位置保存在map中
    • 时间复杂度O(n)
    •  public int[] twoSum(int[] nums, int target) {
           if (nums.length < 2) return new int[0];
           
           Map<Integer, Integer> map = new HashMap<>();
           
           for (int i = 0; i < nums.length; i++) {
               int diff = target - nums[i];
               if (map.containsKey(diff)) return new int[]{i, map.get(diff)};
               map.put(nums[i], i);
           }
           return new int[0];
       }

Knowledge

  1. HashMap

    • 以(key, value)形式存储
    • 无序
    • 每一次的存取都是通过计算一个hash function获得这个key的unique hash值, 这部分是O(1)的,正常情况下使用HashMap的时间复杂度就是O(1),但是如果有collision的话,就是两个key算出来的hash值是一样的,那就是linear 的complexity, 因为一个key里面有两个值, 所以worst的情况O(n)
    • 空间复杂度:每多一对(key, value)就要分配一个空间,所以是O(n)

评论

暂无评论