1.两数之和.md

1.两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

链接：https://leetcode-cn.com/problems/two-sum/

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力破解：

两层for循环，针对每一个数 n，遍历里面是否有另外一个数为target-n。 时间复杂度为O(n^2)，空间复杂度为O(1)。

    public int[] twoSum2(int[] nums, int target) {
        int []result = new int[2];
        for(int i=0;i<nums.length-1;i++){
            for(int j=1;i+j<nums.length;j++){
                if(nums[i]+nums[i+j]==target){
                    result[0]=i;
                    result[1]=i+j;
                }
            }
        }
        return result;
    }

空间换时间

借助hashmap，key为元素的值，value为元素的下标,将数字不断放进hashmap，放之前判断里面是否存在target-num

    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        if (nums == null || nums.length == 0) {
            return result;
        }
        Map<Integer, Integer> numSet = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numSet.containsKey(target - nums[i])) {
                result[0] = numSet.get(target - nums[i]);
                result[1] = i;
                return result;
            } else {
                numSet.put(nums[i], i);
            }
        }
        return result;
    }

复杂度分析：

• 时间复杂度：O(N)，遍历了所有的数。
• 空间复杂度：O(N)，hashMap的大小最大为n。

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。这个世界希望一切都很快，更快，但是我希望自己能走好每一步，写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~