浩哥的力扣刷题记录——1. 两数之和

力扣刷题记录

1. 题目

官网地址：1. 两数之和 - 力扣（LeetCode）

题目截图

2. 讲解

target就是需要求的两个数的和，从数组中排列组合得到两个数加起来正好等于target即可，然后返回其下标。

2.1 思路一

挨个遍历，先拿到数组的第一个数，然后依次加上后面的值进行比较target值，一旦匹配到就输出下标。
本算法就是穷举法，将所有的可能进行计算。

    public int[] twoSum1(int[] nums, int target) {
        int numSize = nums.length;
        // 开始从第一个值开始找
        for (int i=0; i<numSize-1; i++){
            // 找过的值再往下找
            for (int j = i+1; j < numSize; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

显然就是运行效率比较慢一些，因为需要穷举所有可能，最坏的情况就是题目说的O(n^2)

思路一运行结果图

2.12 思路二

可以想一想，我们如果知道一个值a，那另一个值就是target - a了，就是看这个值在不在数组里面，并返回这个值的下标，那么我们两个都知道了。

    public int[] twoSum(int[] nums, int target) {
        // 用来存放散列值，其中key为nums值，value为其下标。
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            // 已知a
            int a = nums[i];
            // 根据target求出b
            int b = target - a;
            // 看看b是不是在数组里面（我们需要用散列值记录），如果在就返回。
            if (map.containsKey(b)){
                return new int[]{map.get(b), i};
            }
            // 如果不在散列值表里面，我们需要添加进去。
            map.put(a, i);
        }
        return new int[]{};
    }

可以看到，使用散列表进行存储时，性能提升很多。

思路二运行结果

3. 参考答案

可以关注笔者的刷题仓库：算法刷题库: 各大OJ算法刷题记录，并将想法思路整理。 (gitee.com)
本源码也包含其中。

/*
 * Copyright (c) Jack魏 2019 - 2022
 */

package com.jackwei.leetcode.t1dt10;

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

/**
 * 作者：Jack魏
 * 题目连接： https://leetcode-cn.com/problems/two-sum/
 *
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回他们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 *
 * 示例:
 * 给定 nums = [2, 7, 11, 15], target = 9
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 */
public class L0001 {
    public static void main(String[] args) {
        int nums[] = new int[]{2, 7, 11, 15};
        int target = 9;
        System.out.println(Arrays.toString(new L0001().twoSum(nums, target)));
    }

    /**
     * 思路一：挨个遍历，先拿到数组的第一个数，然后依次加上后面的值进行比较target值，一旦匹配到就输出下标。
     * 本算法就是穷举法，将所有的可能进行计算。
     *
     * @param nums 数组
     * @param target 目标值
     * @return 数组两个值的下标
     */
    public int[] twoSum1(int[] nums, int target) {
        int numSize = nums.length;
        // 开始从第一个值开始找
        for (int i=0; i<numSize-1; i++){
            // 找过的值再往下找
            for (int j = i+1; j < numSize; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    /**
     * 思路二：可以想一想，我们如果知道一个值a，那另一个值就是target - a了，
     * 就是看这个值在不在数组里面，并返回这个值的下标，那么我们两个都知道了。
     *
     * @param nums 数组
     * @param target 目标值
     * @return 数组两个值的下标
     */
    public int[] twoSum(int[] nums, int target) {
        // 用来存放散列值，其中key为nums值，value为其下标。
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            // 已知a
            int a = nums[i];
            // 根据target求出b
            int b = target - a;
            // 看看b是不是在数组里面（我们需要用散列值记录），如果在就返回。
            if (map.containsKey(b)){
                return new int[]{map.get(b), i};
            }
            // 如果不在散列值表里面，我们需要添加进去。
            map.put(a, i);
        }
        return new int[]{};
    }
}