【Leetcode算法面试题】-1. 两数之和

算法练习

面试经常会遇到算法题目，今天开启算法专栏，常用算法解析

题目

**

**

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

思路

• 遍历数组中的每个元素。 对于每个元素，计算它与目标值的差值。 在数组中查找是否存在这个差值。 如果找到了，返回这两个元素的索引。
• 使用哈希表：通过使用哈希表来存储已经遍历过的数字及其索引，我们可以在 O(1) 的时间内查找某个数字是否存在，从而将时间复杂度从 O(n^2) 降低到 O(n)。
  减少不必要的循环：在找到第一个符合条件的数字对后，立即返回结果，避免了多余的循环。
  更好的错误处理：在返回结果时，检查结果数组的长度，确保它包含两个索引，提高了代码的健壮性。

参考答案

算法1

遍历for循环比较 nums[j] == target - nums[i]

   /**
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{}; // 没有找到符合条件的元素
    }

思考一下有更好的解法吗？
当前时间复杂度为 O(N^2)

算法2

可以通过hash存入Key=value，value=索引的方式存储比较

关键代码

int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{(int) map.get(complement), i};
            } 

/**
     * 在整数数组中找到两个数，它们的和等于给定的目标值
     * 算法优化 O（n） 复杂度
     *
     * @param nums   整数数组
     * @param target 目标值
     * @return 包含两个数索引的整数数组，如果没有找到则返回空数组
     */
    public static int[] optimizedTwoSum(int[] nums, int target) {
        HashMap<Object, Object> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{(int) map.get(complement), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[]{}; // 没有找到符合条件的元素
    }

算法3

上面写完，还有一些细节需要补充

• 异常处理
• map的初始值，内存优化
• 首次不用遍历

 /**
     * 内存优化
     * @param nums
     * @param target
     * @return
     */
    public static int[] optimizedTwoSum2(int[] nums, int target) {
        int length = nums.length;
        // 初始化哈希表
        Map<Integer, Integer> map = new HashMap<>(length-1);
        map.put(nums[0], 0);
        for (int i = 1; i < length; i++) {
            int c = target - nums[i];
            if (map.containsKey(c)) {
                return new int[]{(int) map.get(c), i};
            } else {
                map.put(nums[i], i);
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

执行结果