【LeetCode刷题】1两数之和

为找工作，我的代码都是用的JAVA，慢慢学习中。

LeetCode刷题Day1

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
1
2

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解题方法

1.暴力求解

• 枚举在数组中所有的不同的两个下标的组合
• 逐个检查它们所对应的数的和是否等于target

复杂度分析
时间复杂度:$O(n^2)$，这里n为数组的长度。

空间复杂度:$O(1)$，只用到常数个临时变量。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(nums[i]+nums[j]==target){
                    return new int[]{i,j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");//不写不能通过
    }
    public static void main(String[ ] args){
        int[] arrayName = {2,7,11,15};
        Solution s = new Solution();
        int[] indexs=s.twoSum(arrayName,9);
        for (int i = 0; i < indexs.length; i++) {
            System.out.print(indexs[i]+" ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我自己想到的也是这个暴力破解，因为其他不熟练，但是第一个for循环，我原本写的是(i 这里要说下，java中数组的定义

1. new int[]{1,2,3}
2. int[] nums = new int[5];
nums[0]=1;
3. int[] nums = Array.create(1, 2, 3, 4, 5);//使用Array类的静态方法创建和初始化数组:
4. int[] source = {1, 2, 3, 4, 5};//使用Arrays类的静态方法复制、排序等操作数组:
   int[] target = Arrays.copyOf(source, source.length); // 复制数组
   Arrays.sort(target); // 对目标数组进行排序

对于代码中抛出的异常，要加上这句，是因为，如果数组nums中不存在符合条件的两个数，就不会有返回值，而函数定义的时候，定义的返回类型是int[]，会报错，所以需要抛出异常。
再看看这个异常IllegalArgumentException是非法参数异常，当传递给方法的参数不满足预期时，比如传入了无效的参数或空值，容易引发此异常，如果找不到符合条件的两个数，就抛出这个非法参数异常，错误信息是“No two sum solution”。

2.查找表法

• 在遍历的同时，记录一些信息，以省去一层循环，这是“以空间换时间"的想法

• 需要记录已经遍历过的数值和它所对应的下标，可以借助查找表实现

• 查找表有两个常用的实现:

  • 哈希表

  • 平衡二叉搜索树

复杂度分析

• 时间复杂度:O(n)，这里n为数组的长度。
• 空间复杂度:O(n)，哈希表里最多需要存n-1个键值对。

class Solution1 {
    public int[] twoSum(int[] nums, int target){
        int len = nums.length;
        Map<Integer,Integer> hashMap = new HashMap<>(len-1);
        hashMap.put(nums[0], 0);//这一行也可以不加，因为下面的for循环也会加入的
        for (int i = 0; i < len; i++) {
            int another = target-nums[i];
            if (hashMap.containsKey(another)){
                return new int[]{i,hashMap.get(another)};
            }
            hashMap.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

图片和代码来自leetcode官网

思路：定义一个Map存放键值对，默认将nums[0]添加进去（Map这里用put添加元素），官方给出的代码这边初始化了一下，但在for循环中，nums[0]又被加了一下。

    public static void main(String[] args) {
        Map<Integer,Integer> hashMap = new HashMap<>(5);
        hashMap.put(0,1);
        hashMap.put(0,1);
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }//Key: 0, Value: 1
    }
1
2
3
4
5
6
7
8

我不太了解这个结构，就敲代码试了一下，同样的值加两次，Map他实际第2次会覆盖第1次，应当是按键来存值的，一个键只能一个值。
这里给hashMap赋初值，大概是出于一个程序员的谨慎，就和写文件动不动就ctrl+S一样，hhh。

接着开始遍历，对于nums[0]也就是6，他需要找到一个值为2的，当前Map中没有2，没有就将他存入Map中；对于nums[1]也就是3，他需要找到一个值为5的，当前Map中没有5,没有就将他存入Map中;对于nums[2]也就是8，他需要找到一个值为0的，当前Map中没有0,没有就将他存入Map中;对于nums[3]也就是2，他需要找到一个值为6的，当前Map中有6,找到了，因为题目中说每种输入只会对应一个答案，找到了就返回new int[]{i,hashMap.get(another)}。

再思考一下为什么要将数组的下标和值，将值变为map中的键，下标变为map中的值，大概是因为这样好操作，可以根据值得到我们要的下标。脑子不够用，需要理一下思路。

如有错误，请指正！