leetcode之1-两数之和

暴力

暴力查找，两层 for 循环搞定。唯一要注意的点就是题干要求数组中同一个元素不能使用两遍，所以内层循环要取外层循环之后的元素。

/**
 * 暴力求解
 */
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

两层循环，时间复杂度为 O(n ^ 2)；没有用到额外空间，空间复杂度为 O(1)。

时间复杂度推导：

最好时间复杂度为 O(1)，比如 {2, 7, 11, 15}, target 为 9
最坏时间复杂度为 (n - 1) + (n - 2) + (n - 3) + … + 1 = (n - 1) * (n / 2)，省略低阶和常量，结果为 O(n ^ 2)

两遍哈希表

之前在归并排序的文章中说过，如果数据存储空间不是算法过程中的瓶颈，我们设计的算法通常优先考虑时间复杂度。

本题也可以用空间换时间的思路来进行加速。

那么我们需要一种数据结构，它既可以保存数组中每个元素与其索引的关系，又可以快速的找到某个值的索引。很显然，可以用哈希表。在 java 中我们可以直接用 HashMap。

/**
 * 遍历两遍哈希表
 */
public int[] twoSum(int[] nums, int target) {
    // 规定大小，避免扩容。K->val; V->index
    Map<Integer, Integer> map = new HashMap<>(nums.length);
    // 1.将 nums 中所有值和索引存入哈希表
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    // 2.遍历 nums，在哈希表中寻找 target - nums[i] 的值
    for (int i = 0; i < nums.length; i++) {
        int another = target - nums[i];
        // 注意还要判断一下索引不相同
        if (map.containsKey(another) && map.get(another) != i) {
            return new int[]{map.get(another), i};
        }
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

两遍循环，时间复杂度为 O(2n)，省略常数后为 O(n)；用到额外空间存储数组元素，空间复杂度为 O(n)。

一遍哈希表

时间复杂度已经为 O(n) 了，但是当 n 比较大的时候，这个常数还是会对算法造成一定的消耗。

其实，稍微换一下思路，只遍历一遍数组也能够完成。

在遍历数组时，除了将元素存入到哈希表中，还可以再回头来检查一下哈希表中是否已经存在当前元素所对应的目标元素。

/**
 * 遍历一遍哈希表
 */
public int[] twoSum(int[] nums, int target) {
    // 规定大小，避免扩容。K->val; V->index
    Map<Integer, Integer> map = new HashMap<>(nums.length);
    for (int i = 0; i < nums.length; i++) {
        int another = target - nums[i];
        // 如果哈希表中存在目标元素，返回
        if (map.containsKey(another)) {
            return new int[]{map.get(another), i};
        }
        // 如果哈希表中不存在目标元素，将当前元素存入哈希表
        map.put(nums[i], i);
    }
    // 题干说一定有结果，所以返回 null 也没关系
    return null;
}

一遍循环，时间复杂度为 O(n)；用到额外空间存储数组元素，空间复杂度为 O(n)。

凑字数

这道题还是比较简单的，相信很多人刚开始刷 leetcode 就是从这道题开始，这篇文章就当是回顾一下思路吧。