力扣——001两数之和（简单）

一时失言乱红尘 2023-10-05 09:23 50阅读 0赞

> 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。  
> 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。  
> 示例:  
> 给定 nums = \[2, 7, 11, 15\], target = 9  
> 因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
> 所以返回 \[0, 1\]

**1.暴力解法**，遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素，如下：

public static int[] twoSum(int[] nums, int target) {
        
    		int[] result = new int[2];
    		for (int i = 0; i < nums.length; i++) {
        
    			for (int j = i+1; j < nums.length; j++) {
        
    				if (nums[i] == target-nums[j]) {
        
    					result[0]=i;
    					result[1]=j;
    				}
    			}
    		}
    		return result;
        }
    /********************************************************/  
    复杂度分析：
    时间复杂度：O(n^2)
    对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)
    空间复杂度：O(1)。
    
    补充：
    数组的三种打印方式：
    1、传统的for循环
    for (int i = 0; i < result.length; i++) {
        
    			System.out.println(result[i]);
    		}
    2、foreach循环
    for (int i : result) {
        
    			System.out.println(i);
    		}
    3、利用Array类中的toString方法
    //调用Array.toString(a)，返回一个包含数组元素的字符串，这些元素被放置在括号内，并用逗号分开
    System.out.println(Arrays.toString(result));
    输出：[0,1]

**2.利用哈希表**

> 为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。

*  两遍哈希表  
    略  
    将数组的下标和值作为map的键值对放入，然后再从数组中逐一取值计算，判断是否有对应的key。
 *  一遍哈希表

public static int[] twoSum(int[] nums, int target) {
        
    		// 以值为key，，以下标为value,这样方便判断值是否存在，而且容易根据key获取value（即下标）
    		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    		int[] result = new int[2];
    		for (int i = 0; i < nums.length; i++) {
        
    			int val = target - nums[i];
    			if (map.containsKey(val)) {
        
    				result[0]=i;
    				result[1]=map.get(val);
    				return result;
    			}
    			map.put(nums[i], i);
    		}
    		return result;
        }
    复杂度分析：
    时间复杂度：O(n)，
    我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。
    空间复杂度：O(n)，
    所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n个元素。
    /************************************************/
    补充：map中通过key获取value容易，通过value获取key却没有直接的方法，因为value可重复。
    containsKey（）
    containsValue（）
    get（key）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200831181115909.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NzAzOTc0NQ==,size_16,color_FFFFFF,t_70#pic_center