深圳市建设安监站网站,wordpress是什么程序,岳阳seo招聘,做网站专用图标摘要#xff1a; Leetcode的AC指南 —— 哈希法#xff1a;1. 两数之和。题目介绍#xff1a;给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 文章目录 一、题目二、解… 摘要 Leetcode的AC指南 —— 哈希法1. 两数之和。题目介绍给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 文章目录 一、题目二、解析1、暴力解法2、哈希法 —— 字典 一、题目 题目介绍 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 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]提示 2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案
进阶
你可以想出一个时间复杂度小于 O(n2) 的算法吗
二、解析 1、暴力解法
public static int[] twoSum(int[] nums, int target) {int[] res 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){res[0] i;res[1] j;}}}return res;}时间复杂度O(nlog(n))空间复杂度O(1)
2、哈希法 —— 字典
什么时候使用哈希法当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。哈希法的数据结构 数组数组的大小是受限制的而且如果元素很少而哈希值太大会造成内存空间的浪费。setset是一个集合里面放的元素只能是一个key且无序不重复无索引mapmap是一种key value的存储结构。无序不重复无索引。
思路
创建一个字典key存储访问过的元素value存储该元素对应的数组下标。遍历数组查找访问过的元素中是否有满足两数之和的key 有返回当前元素下标和字典中对应temp的value值也就是temp对应的数组下标没有将当前元素和对应下标存入字典访问下一个元素。
public int[] twoSum(int[] nums, int target) {int[] res new int[2];if(nums null || nums.length 0){return res;}MapInteger, Integer map new HashMap();for(int i 0; i nums.length; i){int temp target - nums[i]; // 遍历当前元素并在map中寻找是否有匹配的keyif(map.containsKey(temp)){res[1] i;res[0] map.get(temp);break;}map.put(nums[i], i); // 如果没找到匹配对就把访问过的元素和下标加入到map中}return res;
}时间复杂度: O(n)空间复杂度: O(n)
