算法练习

面试经常会遇到算法题目，今天开启算法专栏，常用算法解析

题目

**

给定一个整数数组 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]

思路

• 遍历数组中的每个元素。 对于每个元素，计算它与目标值的差值。 在数组中查找是否存在这个差值。 如果找到了，返回这两个元素的索引。
• 使用哈希表：通过使用哈希表来存储已经遍历过的数字及其索引，我们可以在 O(1) 的时间内查找某个数字是否存在，从而将时间复杂度从 O(n^2) 降低到 O(n)。
  减少不必要的循环：在找到第一个符合条件的数字对后，立即返回结果，避免了多余的循环。
  更好的错误处理：在返回结果时，检查结果数组的长度，确保它包含两个索引，提高了代码的健壮性。

参考答案

算法1

遍历for循环比较 nums[j] == target - nums[i]

   /**** @param nums* @param target* @return*/public static int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[j] == target - nums[i]) {return new int[]{i, j};}}}return new int[]{}; // 没有找到符合条件的元素}

思考一下有更好的解法吗？
当前时间复杂度为 O(N^2)

算法2

可以通过hash存入Key=value，value=索引的方式存储比较

关键代码

int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{(int) map.get(complement), i};} 

/*** 在整数数组中找到两个数，它们的和等于给定的目标值* 算法优化 O（n） 复杂度** @param nums   整数数组* @param target 目标值* @return 包含两个数索引的整数数组，如果没有找到则返回空数组*/public static int[] optimizedTwoSum(int[] nums, int target) {HashMap<Object, Object> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[]{(int) map.get(complement), i};} else {map.put(nums[i], i);}}return new int[]{}; // 没有找到符合条件的元素}

算法3

上面写完，还有一些细节需要补充

• 异常处理
• map的初始值，内存优化
• 首次不用遍历

 /*** 内存优化* @param nums* @param target* @return*/public static int[] optimizedTwoSum2(int[] nums, int target) {int length = nums.length;// 初始化哈希表Map<Integer, Integer> map = new HashMap<>(length-1);map.put(nums[0], 0);for (int i = 1; i < length; i++) {int c = target - nums[i];if (map.containsKey(c)) {return new int[]{(int) map.get(c), i};} else {map.put(nums[i], i);}}throw new IllegalArgumentException("No two sum solution");}

执行结果