问题描述

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

解题思路与状态

当时看完题目给自己定了一个30分钟的闹钟，可以在这段时间中搞定它。存在疑问：

  • 若数组排序，可以使用两边夹方法解决之；若不是怎么处理。
  • 数组中是否存在重复元素，若有怎么处理。
  • 未找到满足条件的元素，是抛出异常还是给定特殊的标志，比如[-1,-1]。

看完题目之后头脑中形成的解题思路暴力破解法，一下搞完，本地测试通过了，时间复杂度为 O(n^2)。
不是自己想要的结果，接着想能都把元素的值与下标对应起来，然后再去查找，利用空间换时间，以缩短查询
时间。后面出现了使用hashmap做处理的元素值，这种情况在数组中存在重复元素有问题。后面想了很久
仍旧没有想到使用一个hashmap来解决此问题。这个时候已经过去40分钟，心里面开始出现焦急状态，
无奈之下看答案了。两种hashmap的方法的空间复杂度为O(n),时间复杂度为O(n)。下面就将每个
解法的关键点列出来。

暴力破解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoSum(int[] nums, int target) {
    if (null == nums || nums.length <= 1) {
        return new int[] {-1, -1};
    }
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    return new int[] {-1, -1};
}

双哈希法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] nums, int target) {
    if (null == nums || nums.length <= 1) {
        return new int[] {-1, -1};
    }
    Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < len; i++) {
        int right = target - nums[i];
        if (map.containsKey(right) && map.get(right) != i) {
            return new int[] { i, map.get(right) };
        }
    }
    return new int[] {-1, -1};
}

单哈希法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] twoSum(int[] nums, int target) {
    if (null == nums || nums.length <= 1) {
        return new int[] {-1, -1};
    }
    Map<Integer, Integer> map = new HashMap<Integer,Integer>();
    for (int i = 0; i < len; i++) {
        int right = target - nums[i];
        if (map.containsKey(right)) {
            return new int[] { i, map.get(right) };
        } 
        map.put(right, i);
    }
    return new int[] {-1, -1};
}

总结

以后做算法题或者解决难题的时候，要懂得放一放，不要非得在一定的时间之内完成，特别是在做算法题。
毕竟在leetcode上做算法题不是为了刷题目，而是为了锻炼自己的思维还有夯实算法知识。