leetcode中的两数之和(第一题:简单)

刺骨的言语ヽ痛彻心扉 2021-12-15 09:39 164阅读 0赞

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

*你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。  
示例:  
给定 nums = \[2, 7, 11, 15\], target = 9  
因为 nums\[0\] + nums\[1\] = 2 + 7 = 9 所以返回 \[0, 1\]*

*题意:给一个整形的数，这个数在会在给定数组的两个位置数相加的和！这个和是指值的相加，不是数组的索引相加；如果在数组中有这样的两个数，要求返回两个数的索引(也就是数组的下标)；*

*解法一:暴力方法：应用遍历的方式，应用双重循环，怎么说呢，举个例子 nums = \[2, 7, 11, 15\], target = 9，第一重循环遍历第一个数nums\[0\](值为2)时，在用第二层循环从下标1~3开始遍历，如果下标1~3的值和nums\[0\]相加会等于target:9那么会返回相加两数的下标,如果两重循环结束还没有找到那么就返回null,在这里其实索引和下标的概念是一样的，只是每个人的叫法不一样！* * *

public int[] solutin(int[] nums,int target){
    		for(int i=0;i<nums.length;i++){//1.对每个位置的数进行遍历
    			for(int j=i+1;j<nums.length;j++){//2.对i后面的数进行遍历
    			//这里解释一下，为什么从i的后面开始遍历，不仅仅是为了减少时间复杂度，更是为了一种极端的例子比如:
    			//nums[3,2,6],target=6,如果第二重循环从i本身开始遍历，那么会返回下标[0,0]	
    				if(nums[i]+nums[j]==target){//3.i和后面的每一个数相加值与target比较
    					return new int[]{i,j};//4.如果相加值会等于target，那么就返回相加值在nums数组中的下标
    				}
    			}
    		}
    		return null;//5.两重循环结束表示在数组中没有这样的两个数
    		/**
    		 * 来看一下时间复杂度:在最差的情况下，比如nums[1,2,3,4,5,6,7,8,9,10],target=19;
    		 * 你可以把这个例子带入上面的暴力算法中,得出的肯定是循环9，8，7，6，5，4，3，2，1，
    		 * 这就是一个等差数列，那么最坏情况下时间复杂度就是o(n^2)
    		 * 在来看一下空间复杂度:在这个算法中，只用了有限的变量i和j,那么空间复杂度就是o(1)
    		 */
    	}

时间和空间的展示:

![1680103-20190531132747937-2128096488.png][]

下面介绍一种改进的方法:应用了hash这个性质，其实这查找这个问题里，hash是非常好用的，因为hash插入和删除和查找复杂度都是o(1),在这里我应用了java的hashMap

思路:先把遍历把nums数组的数加入到hashMap中，hashMap中的key存nums中的值，value存入nums中每个值对应的下标，在用一层遍历，从nums数组的开头开始遍历，用target减掉每个nums的值，在用这个减出来的值，在hashMap中查找，如果有，就得到value，最后返回这两个下标，

例子nums\[1,2,3,4\],target=7,先把nums加入到hashMap中，那么hashMap\[\{1,0\},\{2,1\},\{3,2\},\{4,3\}\]，当遍历到下标为2时也就是nums\[2\]=3,用7-3=4，在调用map的containsKey()方法，查询map中有key的值为4吗，这时就有，那么就返回new int\[\]\{2,3\};

public int[] twoSum(int[] nums, int target) {
            if(nums==null){//1.判断给的nums数组是否为空，为null就没有必要进行下面的操作，并且会出现空指针操作
                return null;
            }
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();//2.初始化HashMap集合,为什么用Hash呢就是因为查找的时间复杂度为o(1),这事最低的代价
            for(int i=0;i<nums.length;i++){//3.把nums数组的每个值和下标加入到HashMp中
                map.put(nums[i],i);
            }
            for(int j=0;j<nums.length;j++){//4.从下标0开始遍历nums数组
            	//5.判断target键下标nums[j]的值在HashMap中是否存在，
            	//并且得到的value也就是下标步等于j，这是防止一种情况,nums[3,7,8,2,4]
            	//如果target=6,当j=0时,targt-num[0]=3;在看hashMap是否包含3刚好就是下标0本身，
            	//但是题意说不可重复，一个数字只能用一次，so-----
                if(map.containsKey(target-nums[j])&&map.get(target-nums[j])!=j){
                    return new int[]{j,map.get(target-nums[j])};//6.包含就返回这两个数的下标
                }
            }
            return null;//7.如果没有找到就返回null
            /***
             * 分析时间复杂度两个循环第一个循环为o(n),
             * 第二重循环在最坏的情况nums[0,1,2,3,4,5,6,7],target=13时
             * 时间复杂度为o(n),加在一起O(n),为什么不是2N呢，因为当n很大时2没有意义了，比如n为1千万亿，
             * 那你的机器估计也歇菜了，在估计时间复杂度的时候是去掉常数项的
             * 空间复杂度：因为用了hash这个结构(底层用了数组来存储)，所以空间复杂度为o(n)
             */
        }

复杂度展示

![1680103-20190531224306964-97184937.png][]

跟上面的暴力方法相比，这时间绝对优秀，本来想录一下视频讲一下这题，但是没有时间，下次有时间来哈，有错的地方望大佬纠正

转载于:https://www.cnblogs.com/tranquilityMan/p/10954823.html

[1680103-20190531132747937-2128096488.png]: /images/20211214/e51c029fb8dc4e7397c000be94563c46.png
[1680103-20190531224306964-97184937.png]: /images/20211214/d78c8357d28845fb922eef7902f6360b.png