【两数之和】----LeetCode算法题(一)

6,396 阅读3分钟

一、题目基本信息

题目传送门--两数之和

级别:【简单】
/**
 * 【两数之和】 给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
 * 
 * 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
 * 
 * 示例:
 * 
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 
 * 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
 * 
 * @Author jiawei huang
 * @Since 2019年8月8日
 * @Version 1.0
 */

二、解题思路

  • 1、最简单、最粗暴的方式就是来2层for循环,这种解法时间复杂度为O(n^2) ,不推荐,效率低。

  • 2、由于是两数之和等于某一个数,那么我们很容易就得出一个数学公式A+B=C,我们做一下变换,得到A=C-B,由于我们已知的是C,显然等式2比等式1更加容易求值,同时因为变量有两个,小编想到的是我们一个变量存起来,一个变量进行一次查找比较,因此就有了如下题解思路:

    1、遍历一遍数组,然后将每个值与target做差存起来,同时存该数的下标;

    2、直到找到就返回;

    3、时间复杂度为O(n),空间复杂度也是O(n)

三、代码演示

【解法一】

/**
 * 小编自己的解法:9ms
 * 
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSum(int[] nums, int target) {
    int[] returnArr = null;
    
    // 如果数组是空的,或者数组的长度为0,直接返回
    if (null == nums || nums.length == 0) {
    	return returnArr;
    }
    
    Map</* 差值 */Integer, /* 下标 */ Integer> dataMap = new HashMap<>();
    // 既然要知道目标是第几位,难免要知道数组的下标
    for (int i = 0; i < nums.length; i++) {
    	Integer subNum = nums[i];
    	Integer key = target - subNum;
    	if (dataMap.containsKey(subNum)) {
    		// 注意,赋值操作也是耗时的
    		returnArr = new int[2];
    		returnArr[1] = i;
    		returnArr[0] = dataMap.get(subNum);
    	} else {
    		dataMap.put(key, i);
    	}
    }
    
    return returnArr;
}

【解法二】

/**
 * 针对解法一,小编去除了赋值操作,时间变成6ms
 * 
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSumWithSetValue(int[] nums, int target) {
    // 如果数组是空的,或者数组的长度为0,直接返回
    if (null == nums || nums.length == 0) {
    	return null;
    }
    
    Map</* 差值 */Integer, /* 下标 */ Integer> dataMap = new HashMap<>();
    // 既然要知道目标是第几位,难免要知道数组的下标
    for (int i = 0; i < nums.length; i++) {
    	Integer subNum = nums[i];
    	Integer key = target - subNum;
    	if (dataMap.containsKey(subNum)) {
	    return new int[] { dataMap.get(subNum), i };
    	}
    	dataMap.put(key, i);
    }
    return null;
}

【解法三】

// leetcode大神解法,这解法牛,1ms,但小编没看懂,主要有下面几个疑问,麻烦留言区讨论。
public int[] twoSumOneMs(int[] nums, int target) {
    int indexArrayMax = 2047;
    int[] indexArrays = new int[indexArrayMax + 1];
    int diff = 0;
    for (int i = 0; i < nums.length; i++) {
    	diff = target - nums[i];
    	if (indexArrays[diff & indexArrayMax] != 0) {
    		return new int[] { indexArrays[diff & indexArrayMax] - 1, i };
    	}
    	indexArrays[nums[i] & indexArrayMax] = i + 1;
    }
    throw new IllegalArgumentException("No two sum value");
}

这解法牛,耗时仅1ms,但小编没看懂,主要有下面2个疑问,麻烦留言区讨论。

  • 1、为什么数组大小要设置成2048?
  • 2、为什么与运算&的数据indexArrayMax要选择成20470111 1111 1111而不是其他值?