最简单的算法题，你会吗？

leetcode上算法第一题，求两数之和，是最简单的算法题。

• 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

twosum

1、暴力解法

认真审题之后，我们能想到的最简单的方法就是一个个试，找任意两个数相加，和target比较，直到相等。

    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

这个方法很直观，但是效率不高，双重循环，时间复杂度：n*n

2、巧用哈希

• 我们可以先把所有的数存入hash里面，遍历一次，存入hash有一个好处，取值的时候时间复杂度为O(1)
• 我们用: target - num1,算出余数，再在hash里面查找有没有，再遍历一次

    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++) {
            Integer index = map.get(target - nums[i]);
            if (index != null && index != i) {
                return new int[] {i, index};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

时间复杂度：n*2

3、改进

• 上面用了两次遍历，可不可以一次遍历解决呢？
• 我们可以一边往map放数据，一边计算有没有结果

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

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length ; i++) {
            Integer index = map.get(target - nums[i]);
            if (index != null) {
                return new int[] {i, index};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

关注公众号：丰极，了解更多算法知识。