LeetCode热题100个人学习记录

题目1两数之和

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

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

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

1、网站给出的最优解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int i = 0;                                      //数组起始下标
        int j = nums.length - 1;                        //数组最后下标
 
        Map<Integer, Integer> hash = new HashMap<>(); //建立k-v （k为值，v为该值在数组中对应的下标）
        
        while (i <= j) {//相当于创建了两个指针，直到i=j时停止取值
 
            //1）从头开始取
            if (hash.containsKey(nums[i])) {          //判断当前值之前是否已经存储到了hash表中
            //如果之前已被存储，则nums[i]就等于target-另一个值，
            //相当于两者都已经找到了将其索引存储到index数组中
                int[] index = new int[]{hash.get(nums[i]),i}; 
                return index;
            } else{
                hash.put(target - nums[i], i);        //保存当前值与目标值的差，与其在数组中的索引
            }
 
            //2）从尾开始取
            if (hash.containsKey(nums[j])) {        
                int[] index = new int[]{hash.get(nums[j]),j}; 
                return index;
            } else{
                hash.put(target - nums[j], j);        
            } 
 
            i++;
            j--;
 
        }
        return null;            
    }
}

index是一个一维数组，放进去的只有索引位置；

若数组nums声明为[1,2,3,4]，target = 6，从后往前遍历到4的时候就已经把<2,3>放进了map中，target - nums[3] = 2, j = 3。所以在从前往后遍历到2时，发现map中已经存在了，执行int[] index = new int[]{hash.get(nums[i]),i};这行代码，而hash.get(2)得到是在map中key=2的位置对应的value，也就是刚才存入的<2,3>中的3,其实就是j值，因此最后index数组中存入的是两个索引值。

2、解决方式二：用map存放数组，但单向遍历

class Solution {
    public int[] twoSum(int[] nums, int target) {
/ //用地图存放数组，查阅起来更快速
		 Map<Integer, Integer> map = new HashMap<Integer,Integer>();
	     for(int i=0;i<nums.length;i++) {
		 	map.put(nums[i], i);
		 }
		 for(int i=0;i<nums.length;i++) {
		 	//用目标数字-当前数字就是还差多少
		 	int remainder=target-nums[i];
		 	if(map.containsKey(remainder)&&map.get(remainder)!=i) {
		 		//如果当前地图中存在这样一个数字，并且它对应的下标与当前扫描到的数字不同
		 		//说明找到了
		 		return new int[] {i,map.get(remainder)};
			}
		 }
         return null;
}
}

3、解决方式一：自己写的两层for循环暴力解

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for(int i = 0;i <= nums.length;i ++){
            for(int j = i + 1;j < nums.length;j++){
                if(nums[i] + nums[j] == target){
                  arr[0] = i;
                  arr[1] = j;
                  return arr;  
        }
 
    }
  }