【Leetcode-1】Two Sum（两数之和）

Github：Leetcode-1. Two Sum(代码实现)

Leetcode-1. Two Sum

 在数组中找 2 个元素，他们的和等于给定目标值，结果返回这 2 个元素对应的数组下标。

遍历数组，通过目标值与每个元素做差，计算目标值的“另外一半”，在 Map 中查找“另外一半”，

如果找到，则返回 2 个元素的对应数组下标。如果找不到，则将“另外一半”放入 Map 中，

等待下次遍历找到另外一半的时候取出来并返回。

package com.jpeony.leetcode.n0001;

import java.util.Arrays;
import java.util.HashMap;


public class N1_TwoSum {
    
    private static int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if (map.get(x) != null) {
                return new int[]{map.get(x), i};
            }

            map.put(nums[i], i);
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] resTwo = twoSum(nums, target);
        System.out.println("哈希表：" + Arrays.toString(resTwo));
    }
}

map 存入值时，注意 key 是数组元素值，value 是元素在数组中的对应下标位置。

时间复杂度：O(n)。整个代码循环了 n 次，n 为数组的长度，所以时间复杂度为 O(n)；

空间复杂度：O(n)。每次遍历都往 map 存放一次元素，遍历次数 n 为数组长度，所以空间复杂度为 O(n)；