Day1 两数之和

两数之和 https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍

你可以按任意顺序返回答案。
示例 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]

Java算法

思路：

• 错误思路：初始以为是有序数组，想用target缩短nums数组长度，再使用减值遍历
• 成功思路
  1. 使用HashMap存储下标index及与target的差值
  2. nums遍历时，在存储之前先查找是否已存储差值为当前遍历值相同的数据，有则返回，无则继续
  3. 其实数组中同一个元素不能使用两遍已经隐晦的提示用差值来进行操作，奈何刚开始没看懂

package sj.shimmer.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by SJ on 2021/1/25.
 */
class D1 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 4};
        int target = 6;
        int[] results = twoSum(nums, target);
        for (int i = 0; i < results.length; i++) {
            System.out.println(i + "=" + results[i]);
        }
    }
    /**
     * 用HashMap来存储 index 和补全target需要的int值，在遍历过程中，添加之前先查询有没有补全值相等的数据，有表示找到，返回这两个下标
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return nums;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                if (entry.getValue() == nums[i]) {
                    return new int[]{entry.getKey(), i};
                }
            }
            int value = target - nums[i];
            map.put(i, value);
        }
        return nums;
    }
}

image.png

官方解

1. 暴力枚举
   比较每一个数x，寻找是否存在target-x

   时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

   空间复杂度：O(1)。

2. 哈希表，即我采用的方法，但官方使用差值作为key，下标作为value

   时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以O(1) 地寻找 target - x。

   空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。