LeetCode第一题 两数之和
2021年3月4日
两数之和
给定一个整数数组 nums和一个整数目标值 target ，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。(这个使用两遍，7和7=14 时不行的这个就输出[n.n]这种，当时我的理解时，这个数组内的数只能用一次，就是遍历一次就已经用过一次了。这种想法)
你可以按照任意顺序返回答案；
示例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<=mums.length<=10^3
-10^9<=nums[i] <=10^9
-10^9<=target<=10^9
只会存在一个有效答案
自己思路：
首先想到的是用循环遍历 ok，写下
public class Solution_01 { public static int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for (int i = 0; i < nums.length - 1; i++) {// 先来个顶点索引 for (int j = 1; j < nums.length; j++) {// 除了第一个素组，一次擦找对应匹配对， if (target == (nums[i] + nums[j])) { result[0] = i; result[1] = j; return result;// 匹配成功返回 } } } return result; }
问题是解决的一半
（后续）上面的代码优化 j=nums.length-1,这样循环就有少了点次数（精彩）。
别人家的孩子代码：
public static int[] twoSum(int[] nums, int target) { // 注重实际情况，先判断检查一下 if (nums == null || nums.length == 0) return new int[0]; // 先来个顶点索引 for (int i = 0; i < nums.length; i++) { int x = nums[i]; // 在其后顶点查找，线性查找 for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - x) { return new int[] { i, j }; } } } return new int[0]; }
空间复杂度：因为不开辟空间，所以空间复杂度为o(1)
时间复杂度：需要计算那个语句的最多执行的次数 0(n^2)
时间复杂度技术：(n-1)+ n(n-2)+...+1
在次优化：不用线性查O(n)找用二分查找o(log n)
思路：如果用二分找，就发现下标就会重新排序，虽然值时一样的，但是下标却变了。
所以要开辟空间用map<内容值，数组下标值>。解决了排序后还能找到以前数组的对应下标
空间复杂度：开辟空间O(n)
时间复杂度：O(nlog n)
复习 二分查找（折半查找）：
二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
再次优化用hash查找
复习下 hashMap
public static int[] twoSum1(int[] nums, int target) { // 注重实际情况，先判断检查一下 if (nums == null || nums.length == 0) return new int[0]; // 数据先处理下 第一个疑惑：这时不是就用了一次（重复值问题） HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // 0(n) map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) {// O(n) int x = nums[i]; // 哈希查找 0(1) if (map.containsKey(target - x)) { int index = map.get(target - x); // i和index不是同一个元素，同一个元素不能使用两次 if (i != index) return new int[] { i, index }; } } return new int[0]; }
最终的答案：
public static int[] twoSum2(int[] nums, int target) { // 注重实际情况，先判断检查一下 if (nums == null || nums.length == 0) return new int[0]; // 数据先处理下 第一个疑惑：这时不是就用了一次（重复值问题） HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) {// O(n) int x = nums[i]; // 哈希查找 0(1) if (map.containsKey(target - x)) { int index = map.get(target - x); // i和index不是同一个元素，同一个元素不能使用两次 // if (i != index)//不用这个的原因是后添加的数根本就不会检测到重复的数值（下标索引是否重复） return new int[] { i, index }; } map.put(x, i); } return new int[0]; }