LeetCode#1

题目

原始地址：https://leetcode.com/problems/two-sum/

public class Solution {
    public int[] twoSum(int[] nums, int target) {

    }
}

描述

给定一个int数组和一个指定的值target，要求找出数组中和为target的两个数（只有一组），并返回这个两个数的index值。

分析

看到题目最直接想到的是O(N²)的解法：遍历整个数组，取出nums[i]的值a，再查找nums[j]的值为(target-a)，最终得到i和j的值。然而这样的时间复杂度显示是不能令人满意的。那么我们考虑一下，如何优化算法呢？

本题目中，搜索效率是问题的关键。如何提高搜索效率呢？当然是哈希表。由于题目已经保证有且只有一组解，那么我们可以用每组键值对保存数组中的一个数值和其对应的index，这样查找只需要O(1)即可完成，整体的时间复杂度为O(N)。

解答

public class Solution {
    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[]{i, map.get(complement)};
            } else {
                map.put(nums[i], i);
            }
        }
        throw new RuntimeException("There's no solution.");
    }
}