Leetcode打卡8：题号1：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案

题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

理解

1.暴力解法，无非就是双层的for循环，寻找是否有相加等于target的两个值，记录下标并返回

2.对于最后一个题目要求，不能重复利用这个数组中同样的元素，其实我认为这道题目本身就是有歧义的，有两种不同的理解方式：
第一种就是数组中不能是同一个下标的值相加两次等于target
第二种就是数组中不能用相同的元素相加等于target
经过我的测试，发现这个题目要求的是第一种要求！

3.算法优化，对于暴力解法中的外层for循环是不可避免的，但是内层for循环是否可以进行优化呢？因为内层for循环的作用是在数组中寻找target-num[i]的值，用for循环的话时间复杂度为O（n），但是如果用hashmap来做的话时间复杂度就会减少了，一般来说hashmap查找的效率是O（1），最复杂的时候是O（n）

暴力算法实现

public static int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            for(int j = i+1; j < nums.length; j++){
                if(temp == nums[j] ){
                    return new int[] {i,j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

优化算法的实现

算法设计：

1.创建一个hashmap，先将数组中的第一个数传进去（num[0]，0）
2.每次遍历的时候寻找这个map中是否存在key等于target-num[i]，如果不存在就继续将数组中的值传进去（num[i]，i）
3.直到找到了值，就进行输出即可

设计原则：

1.外层循环的时间复杂度是不变的
2.内存循环从查找数组改成了查找hash表，对于hash表的查找时间复杂度（也就是hashMap.containsKey方法的实现）大家可以上网看一下，一般来说是O（1）
3.但是同时我们的空间复杂度的确是增加了，也就是用空间换时间的经典思想

public static int[] twoSum1(int[] nums, int target) {
    HashMap hashMap = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];
        if(hashMap.containsKey(temp)){
            int index1 = (int)hashMap.get(temp);
            return new int[] {index1,i};
        }
        hashMap.put(nums[i],i);
    }
    throw new IllegalArgumentException("No two sum solution");

}

刷题总结

1.第一次不使用自动语法补充的编程有点不熟悉，首先就是数组的定义和初始化，实际上创建数组有三种方式
第一种：
int[] a = new int[6];
第二种：
int[] x={1,2,3,4};
第三种：也是我这里使用的，其实以前也没见过这样创建的
int[] y= new int[]{1,2,3,4,5};
这是我需要学习的！

2.第二就是数组的长度是关于数组的属性length，而hashmap和list数组的大小都是调用方法size()

3.这里为什么最后要抛出一个异常，因为如果不抛出这个异常程序无法运行，会显示缺少return

4.hashMap.containsKey方法，也就是查找hash表的实现，其实我之前学习过，使用hash值去与上一个值，这个值有点忘记了，所以时间复杂度是0（1）