【两数之和】----LeetCode算法题（一）

秒速五厘米 2024-04-17 06:30 87阅读 0赞

#### 一、题目基本信息 ####

[题目传送门--两数之和][--]

级别：【简单】
    /**
     * 【两数之和】 给定一个整数数组 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`要选择成2047`0111 1111 1111`而不是其他值？

转载于:https://juejin.im/post/5d512e8df265da039d32c046

[--]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Ftwo-sum%2F