1. 两数之和

LeetCode 1. 两数之和

方法一：暴力枚举

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

public class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        int len = nums.length;  //数组长度
        for(int i=0;i<len-1;i++){
       //注意len-1
            for(int j=i+1;j<len;j++){
       //注意j=i+1，之前的元素不需要再匹配;j<len
                if(nums[i]+nums[j]==target){
    
                    return new int[]{
    i, j}; //返回int[]
                }
            }
        }
        return new int[0];	//返回异常或空
    }
}

方法二：查找表法-哈希表

思路：数组中的每一个数 x，寻找数组中是否存在 target - x

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)

创建一个哈希表，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配

public class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        /*方法二：查找表法（哈希表）*/
        int len = nums.length;  //数组长度
        HashMap<Integer,Integer> hashMap = new HashMap<>(len-1); //定义哈希表，初始容量
        hashMap.put(nums[0],0); //第一个值hash表中没有配对值，直接存放
        for(int i=1;i<len;i++){
    	//注意i=1
            int another = target-nums[i];   //获取配对
            if(hashMap.containsKey(another)){
       //hash表中找到配对值
                return new int[]{
    hashMap.get(another),i};   //返回i以及配对值的关键字
            }
            hashMap.put(nums[i], i);    //没有配对，存放到哈希表，i+1；
        }
        return new int[0];	//返回异常或空
    }
}