力扣题库1、两数之和

妖狐艹你老母 2022-10-05 14:56 130阅读 0赞

### 两数之和 ###

*   *  0、楔子
     *  1、查看题目
     *  2、思路分析
     *  3、代码实现(java)

## 0、楔子 ##

哈喽，好久不见，拖延癌又犯了，一不小心就过去了一个多月，直到今天，一个朋友给我私信，我发现自己已经拖更这么久了，说来惭愧，我以前写博客最大的憧憬就是能够进入周榜前100，然而当我到达了200左右的时候…我拖延症犯了o(╥﹏╥)o，这一次，我一定要冲到前100，冲鸭，算法学起来。

## 1、查看题目 ##

[点我穿越][Link 1]

## 2、思路分析 ##

首先，分析题目,它的要求是随机获取一个数组，根据指定的值来获取数组里的两个加数的索引，并返回其数组的形式。同时，它还要求**数组中同一个元素在答案里不能重复出现**，这就意味着目标值的加数不能是两个相同的数。这一点，是解这道题的关键。以下参考力扣官方的解题思路：

根据该题的特效，很明显我们需要去比较每一个元素，假设使用暴力破解，我们用目标值减去数组的第一个元素，然后拿这个值去与其他的元素进行比较，它的时间复杂度是为O(n^2)，但是，题目的要求是要小于O(n ^2)的，所以，暴力法虽然能得出正解，但是时间复杂度是不能满足要求的，这时候，我们就需要对算法进行优化，回过头来，我们再来考虑该题的特性，就是需要通过遍历每一个值然后不断的去比较，查找对应的值，而适合查找的数据结构，无疑就HashTable了，理想的情况下，HashTable查找元素的效率为O(1)，所以，当我们去使用HashTable来解决这道题时，它的理想速率为O(n)，是完全符合题目的要求的。我们先将数组的每一个元素与其对应的索引存入哈希表中，然后遍历数组，获取每一个元素与当前目标值的**差值**，根据这个差值去哈希表中查询对应的元素，若存在改值，则记录其索引，如不存在，则继续查找下一个差值。

## 3、代码实现(java) ##

package workStudy;
    
    import java.util.Hashtable;
    
    import com.fufu.util.ArraysUtil;
    
    public class 两数之和 { 
    	
    	public static void main(String[] args) { 
    		//14 10 7
    		int nums[] = { 1,5,8,9,15,7,8};
    		两数之和 lszh = new 两数之和();
    		int[] indexs = lszh.twoSum(nums, 15);
    		ArraysUtil.arrayPaint(indexs);
    		
    	}
    	
    	public int[] twoSum(int[] nums, int target) { 
    			//创建哈希表
    	       Hashtable<Integer,Integer> h = new Hashtable<Integer, Integer>();
    	       //将数组的每一位元素与其对应的索引存入哈希表
    	       for(int i=0;i<nums.length;i++){ 
    	           h.put(nums[i],i);
    	       }
    	       //设置目标元素的索引容器
    	       int indexs[] = new int[2];
    	       
    	       for(int i=0;i<nums.length;i++){ 
    	    	   //获取目标值减去当前元素的差值
    	           int diff = target - nums[i];
    	           //h.containsKey(diff):判断是否存在与diff相等的元素
    	           //h.get(diff):虎丘diff对应的索引
    	           if(h.containsKey(diff)&&(int)h.get(diff)!=i){ 
    	               indexs[0] = i;
    
    	               indexs[1] = (int)h.get(diff);
    	                return indexs;
    	           }
    	       }
    	        return null;
    	    }
    
    }

[Link 1]: https://leetcode-cn.com/problems/two-sum/