一、背景
最近由于个人原因，比较繁忙，陷入了前端的陷阱无法自拔，搞各种自己没有接触过的语言，修改vott打标签工具的源码、监控摄像头的web实时显示，其痛苦程度罄竹难书...索性熬过来了，真好，发现自己的学习能力真的还挺不错的，然后这个阶段的繁忙时光总算熬过去了。计划逼着自己搞搞人工和算法，先算法入门小题来一波，纪念一下。
二、题目描述
给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
三、思路及解法
- 数组遍历,暴力解法
class Solution { public int[] twoSum(int[] nums, int target) { if(nums.length == 2){ return new int[]{0,1}; } 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; break; } } } return arr; } }
执行结果展示：
执行结果：通过 显示详情 添加备注 执行用时：10 ms, 在所有 Java提交中击败了11.28%的用户 内存消耗：38.2 MB, 在所有 Java 提交中击败了97.99%的用户
- map解法
class Solution { public int[] twoSum(int[] nums, int target) { if(nums.length == 2){ return new int[]{0,1}; } int[] arr = new int[2]; Map<Integer,Integer> maps = new HashMap<>(nums.length); for(int i = 0 ;i<nums.length;i++){ maps.put(nums[i],i); } for(int i=0;i<nums.length;i++){ Integer des = maps.get(target-nums[i]); if(des != null){ arr[0] = i; arr[1] = des; if(i != des){ return arr; } } } return arr; } }
执行结果展示：
执行结果：通过 显示详情 添加备注 执行用时：4 ms, 在所有 Java 提交中击败了19.90%的用户 内存消耗：38.8 MB, 在所有 Java 提交中击败了19.73%的用户
- 比较法
class Solution { public int[] twoSum(int[] nums, int target) { if(nums.length == 2){ return new int[]{0,1}; } int left = 0; int right = nums.length - 1; List<Integer> maps = new ArrayList<>(nums.length); for(int i = 0;i<nums.length;i++){ maps.add(nums[i]); } Arrays.sort(nums); while((nums[left]+nums[right])!=target){ if((nums[left]+nums[right]) > target){ right--; } if((nums[left]+nums[right]) < target){ left++; } } return new int[]{maps.indexOf(nums[left]),maps.lastIndexOf(nums[right])}; } }
执行结果展示：
执行结果：通过 显示详情 添加备注 执行用时：4 ms, 在所有 Java提交中击败了19.90%的用户 内存消耗：38.1 MB, 在所有 Java 提交中击败了99.71%的用户
- 大佬的Map进化版（查阅答案获得）
public class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]),i}; } else { map.put(nums[i], i); } } return new int[0]; } }
执行结果展示：
执行结果：通过 显示详情 添加备注 执行用时：0 ms, 在所有 Java提交中击败了100%的用户 内存消耗：38.4 MB, 在所有 Java 提交中击败了89.40%的用户
