LeetCode第一题“两数之和”（梦开始的地方~）

“有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。”

“两年前第一次刷leetcode，第一题就不会。两年后的今天重刷第一题还是不会，我还是以前的我，不忘 初 心，没有一丝丝改变。”

逛力扣的时候发现的，挺好玩的······

然后看看LeetCode第一题难在哪里吧！

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 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]

方法一：（暴力遍历法）

先给大家讲解一下这张图：

1. 定义两个指针，一个指向第一个元素（i），另一个指向第一个指针的后一个元素（j）（确保数组中的同一个元素在答案里不能重复出现），再把两个指针对应的元素想加，和目标值比较，相等则返回两个指针，不相等则进行下一步。
2. i 指针位置不变，j 指针向后面一动一位，再把两个指针对应的元素想加，和目标值比较，相等则返回两个指针，不相等则进行下一步。
3. i 指针位置不变，j 指针向后面一动一位，再把两个指针对应的元素想加，和目标值比较，相等则返回两个指针，不相等则进行下一步。
4. 因为 j 指针把数组里面的元素全部一一对应完，i 指针后移一位，j 指针又变为 i 指针的后一位，再把两个指针对应的元素想加，和目标值比较，相等则返回两个指针，不相等则进行下一步。
5. i 指针位置不变，j 指针向后面一动一位，再把两个指针对应的元素想加，和目标值比较，相等则返回两个指针，不相等则进行下一步。
6. 因为 i 指针和 j 指针的已经把数组里面的元素全部一一对应完，结束循环。如果符合要求，就返回两指针；如果不满足要求，则不反悔任何元素（本题已经明确说明只会有一种对应的答案，因此不考虑其他因素）

下面是LeetCode运行的代码：

public static int[] twoSum2(int[] nums, int target) {
        int i = 0;
        int j = i+1;
        int[] result = new int[2];

        while(i < nums.length && j < nums.length){
            if(nums[i] + nums[j] == target){
                result[0] = i;
                result[1] = j;
            }
            j++;
            if(j == nums.length){
                i++;
                j = i+1;
            }

        }

        return result;
    }

这是我们自己编译器或者idea里面测试的代码：

public class Function {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        System.out.println("[" + twoSum2(nums, target)[0] + "," + twoSum2(nums, target)[1] + "]");
    }
    
    public static int[] twoSum2(int[] nums, int target) {
        int i = 0;
        int j = i+1;
        int[] result = new int[2];

        while(i < nums.length && j < nums.length){
            if(nums[i] + nums[j] == target){
                result[0] = i;
                result[1] = j;
            }
            j++;
            if(j == nums.length){
                i++;
                j = i+1;
            }

        }

        return result;
    }
}

方法二：（has表查找法）

先看看下面的图：

步骤：

1. 定义一个HasMap（集合），数组里面的元素为key（键），对应的索引为value（值）。
2. 遍历数组，再定义一个临时变量diff，要求diff ＝ target - nums[i]，并且判断diff是否在HasMap中（还需要判断 i 是否与HasMap中对应的值相等），如果diff在has表，并且diff对应的索引与has表中对应的 value 不相等，则返回 i 和value；如果不相等，则 i + 1，继续判断。知道数组中的元素全部比较完，再结束循环。

下面是LeetCode中实现代码：

public static int[] towSum(int[] nums,int target){
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] result = new int[2];
        //创建Has表
        for (int i = 0; i < nums.length;i++) {
            map.put(nums[i],i);
        }
        for (int j = 0; j < nums.length; j++) {
            int diff = target -nums[j];
            if (map.containsKey(diff) && map.get(diff)!=j) {
                result[1] = j;
                result[0] = map.get(diff);
            }

        }
        return result;
    }

下面是idea或者我们自己编译器测试的代码：

import java.util.HashMap;

public class Function {
    public static void main(String[] args) {
        int[] nums = {2,7,11,15};
        int target = 9;
        towSum(nums,target);
        System.out.println("["+towSum(nums,target)[0]+","+towSum(nums,target)[1]+"]");

    }
    public static int[] towSum(int[] nums,int target){
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] result = new int[2];
        //创建Has表
        for (int i = 0; i < nums.length;i++) {
            map.put(nums[i],i);
        }
        for (int j = 0; j < nums.length; j++) {
            int diff = target -nums[j];
            if (map.containsKey(diff) && map.get(diff)!=j) {
                result[1] = j;
                result[0] = map.get(diff);
            }

        }
        return result;
    }
}

总结：

LeetCode 第一题思路不是很难想，但是多小伙伴第一次接触这种刷题方式，才会无从下手（只写方法或者函数，不需要mian这个方法或者函数）。小伙伴们不要怕，多多练…一杯茶，一支烟，一道leetcode是一天……