文章目录

一、题目1. 题目描述2. 示例3. 题目解析 二、解法1. 个人解法（1）代码（2）失败反思（3）改进（4）解法分析（5）提交截图 2. 官网高星解法（1）哈希表解法分析代码算法分析提交截图

一、题目

1. 题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

2. 示例

示例1： 给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 示例2： 给定 nums = [-3, 7, 3, 15], target = 9

因为 nums[0] + nums[2] = -3 + 3 = 0 所以返回 [0, 2]

3. 题目解析

题目中给定的要求是，一个元素不能使用两遍，对输入数组的要求是整数，这里要注意可以输入负数或者正数。

二、解法

1. 个人解法

（1）代码

int[] twoSum1(int[] nums,int target){ // 初始化结果数组 int[] result=new int[2]; // i，j为两个指针 for(int i=0;i<nums.length;i++){ // 去除大于target的数 if(nums[i]>target){ continue; } for(int j=i+1;j<nums.length;j++){ // 去除大于target的数 if(nums[j]>target){ continue; } // 找到后给result数组赋值 if(nums[i]+nums[j]==target){ result[0]=i; result[1]=j; return result; } } } return result; } public static void main(String[] args){ int[] nums={-3,0,3,4}; int target=0; ArraySum arr=new ArraySum(); int[] result=arr.twoSum1(nums,target); for(int num:result){ System.out.println(num); } }

（2）失败反思

不能盲目的加限制条件： 做题的时候为了减少时间复杂度，在循环里给遍历到的元素加了一个限制：如果大于target，就跳过。忽略了数组里可以有正数，负数同时存在的情况。

（3）改进

/** * 去掉了之前的限制 * @param nums * @param target * @return */ int[] twoSum2(int[] nums,int target){ // 初始化结果数组 int[] result=new int[2]; // i，j为两个指针 for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length;j++){ // 找到后给result数组赋值 if(nums[i]+nums[j]==target){ result[0]=i; result[1]=j; return result; } } } return result; }

（4）解法分析

未想到其他可以减少时间复杂度的算法，只能先将之前的代码中的限制去掉，用时间复杂度为$O(n^2)$的双层遍历算法先尝试提交。解法太过小白，在此不展开分析。

（5）提交截图

第一次提交： 改进后的提交：

2. 官网高星解法

（1）哈希表

解法分析

使用哈希表的便利之处在于，哈希表查找、插入和删除的最优时间复杂度是$O(1)$（有哈希冲突会增加），因此，只需要一次遍历结合哈希表的查找，即可完成任务。但是将元素放入哈希表，需要额外的空间。

代码

public int[] twoSum(int[] nums, int target) { // 初始化结果数组 int[] result = new int[2]; // map里键值对存的是<值,id> Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // 判断map里有木有合适的key if (map.containsKey(target - nums[i])) { // 有的话直接返回结果 result[0] = map.get(target - nums[i]); result[1] = i; return result; } else { // 没有合适的key那就把当前项再加入map map.put(nums[i], i); } } return result; }

算法分析

时间复杂度：$O(n)$ 空间复杂度：$O(n)$

提交截图