Leetcode#1.Two Sum（两数之和）

题目描述

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

思路一：

暴力

思路二：

用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i] ，如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。

代码实现

package Array; import java.util.Arrays; import java.util.HashMap; /** * 两数之和 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 */ public class Solution1 { public static void main(String[] args) { Solution1 solution1 = new Solution1(); int[] nums = {2, 7, 11, 15}; int target = 9; int[] result = solution1.twoSum(nums, target); System.out.println(Arrays.toString(result)); } /** * 用 HashMap 存储数组元素和索引的映射，在访问到 nums[i] 时，判断 HashMap 中是否存在 target - nums[i] * 如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。 * 该方法的时间复杂度为 O(N)，空间复杂度为 O(N)，使用空间来换取时间。 * * @param nums * @param target * @return */ public int[] twoSum_2(int[] nums, int target) { HashMap<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 null; } /** * 暴力，时间复杂度为 O(N^2) * * @param nums * @param target * @return */ public 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[i] + nums[j] == target) { return new int[]{i, j}; } } } return null; } }