Java实现每日一道算法面试题（1）：leetcode1两数之和

算法在编程领域的重要性不言而喻，而且也是好多大厂面试经常要考核的重点。

1.两数之和

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

算法思路：

1. 暴力法：使用两层循环，外层循环计算当前元素与 target 的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标；

时间复杂度：O(n^2)

2. 利用HashMap减少查询时间：HashMap 可以根据下标快速查找数据，减少了查询时间，结合这个特性使用一层循环即可以实现：每遍历一个元素就计算该元素与 target 之间的差值，然后到 HashMap 中查找该差值，如果找到则返回两个元素的下标，如果没有找到，则将元素存入 HashMap 中（Key：nums[i]，Value：i）；时间复杂度：O(n)。

算法代码：根据算法思路2，写出的算法具体代码如下：

    /**
     * 两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i ++) {
            int value = target - nums[i];
            if (map.get(value) != null) {
                res[0] = map.get(value);
                res[1] = i;
            }
            map.put(nums[i], i); // 构建 HashMap
        }
        return res;
    }

  如果你有疑问或更好的算法思路，欢迎留言交流！！！
  如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！