LeetCode_1 两数之和 (数组题)

题目地址：https://leetcode-cn.com/problems/two-sum/

题目：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

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

试题分析：

这道题主要考察的是数组的基本操作，我相信大家第一时间想到的肯定是嵌套循环暴力计算，但是这样嵌套两层循环的时间复杂度也是显而易见的差达到了O(n^2)，但是这样的性能太差了，下面我说下比较好的实现可以做到O(n)，只要循环一次就行了，当循环到当前值的时候，那么他要寻找的数字是加起来等于目标值的，也就是需要寻找数字＝目标值－当前循环值，怎样查找的效率最高，那当然是hash表，根据key可以做到O(1)，那么我们可以将数组放到hashmap中，将数值作为key，数组下标作为value，如果在循环体中判断map中包含key为目标值－当前循环值的节点并且不是循环值本身就取出循环值和map中符合条件的节点的下标作为返回。

代码：

public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        Map map = new HashMap(nums.length);
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],i);
        }
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i]) && !map.get(target-nums[i]).equals(i)){
                result[0] = i;
                result[1] = (Integer) map.get(target-nums[i]);
                break;
            }
        }
        return result;

源码路径：com.monkey01.array.TwoSum_1

配套测试代码路径：test目录com.monkey01.array.TwoSum_1Test

https://github.com/feiweiwei/LeetCode4Java.git