数组算法题 - 两数之和

两数之和

刷题时间:

• 25/12/20

我的解法

▼
java
复制代码
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        if (len < 2)
            return null;

        int[] result = new int[2];

        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    break; //这里仅仅跳出了内存循环, 如果要跳出外层循环,应该设置标记
                }
            }
        }

        return result;
    }
}

优点:

• 边界处理正确(len < 2)
• 使用了j = i + 1避免重复配对

缺点:

• O(n^2)的时间复杂度过高, 可能会超时
• 没有充分利用题目信息:"保证存在解", 可以不判断边界
• bug: 找到答案后break只跳出了内层循环, 跳出外层循环需要设置标记

优化:

▼
java
复制代码
class Solution {
    public int[] twoSum(int[] nums, int target) {
		// 更简洁的边界判断
		if(nums == null || nums.length < 2)
			return new int[0];  //返回空数组而不是null

        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j}; //直接返回
                }
            }
        }

        return new int[0];  //题目保证有解, 不执行
    }
}

题解

▼
java
复制代码
class Solution {
    public int[] twoSum(int[] nums, int target) {
	    // key = 数值, value = 下标
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int gt = target - nums[i];

			// 检查补数是否出现过
            if (map.containsKey(gt)) {
                return new int[] { map.get(gt), i };
            }

			// 将当前数值与下标存入哈希表, 这行代码需要放在后面, 防止自己配对自己
            map.put(nums[i], i);
        }

        return new int[0];
    }
}

1. 思路:

   • 暴力解法的时间复杂度是O(n^2), 空间复杂度是O(1)
     • 如何优化,要么减少时间复杂度,要么减少空间复杂度, 在程序运行中,往往时间复杂度的优化要优先于空间复杂度
     • 那么就优化时间复杂度到O(n).
   • 两层for循环,减少到一层for循环即可
     • 那么"找两个数的和等于target"可以转变为: "对于nums[i], 查找target - nums[i]是否出现过"
     • 可以采用哈希表, 使用哈希表来存储出现过的nums[i],key存储nums[i],value存储i(索引)
     • 在内循环中,判断map中是否存在key = target - nums[i], 如果存在,则输出结果(两个索引)
       • 如果不存在, 则将nums[i]存入map, 等待被匹配
   • 哈希表法的时间复杂度是O(n), 空间复杂度是O(n).
     • 这就是用空间换时间

2. 算法思想

   • 用空间换时间 - 哈希表
   • 为什么要这样设计哈希表: key = 数值, value = 下标
     • map.containsKey()可以判断是否存在键, 而题目需要判断的就是是否存在target - nums[i].
     • 题目需要返回的是索引, 那么value就可以通过key获取索引
   • 为什么不能"先全加入map, 再查找"?
     • 可能导致自己匹配自己的情况: (如[3],target=6).
     • 所以要边查边存
   • 边界条件
     • 在我的解法中, if (len < 2) return null; 题目保证有解, 这是可以不判断的
     • 但是这样的编程习惯是好的!