No.0001 Two Sum
https://leetcode-cn.com/problems/two-sum/
方法一 暴力法
复杂度:
- 时间复杂度:
对每个元素都遍历数组的剩余部分来找到剩余值满足目标,需要耗费 的时间 - 空间复杂度:
class Solution { 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] == target - nums[j]) { return new int[] {i, j}; } } } return null; } }
方法二 两次哈希表
复杂度
- 时间复杂度:
遍历容量为n的数组两次,哈希表查找时间: - 空间复杂度:
表中需要储存n个元素class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int res = target - nums[i]; if (map.containsKey(res) && map.get(res) != i) { return new int[] {i, map.get(res)}; } } return null; } }
方法三 一次哈希表
复杂度
- 时间复杂度:
遍历容量为n的数组一次,哈希表查找时间: - 空间复杂度:
表中需要储存n个元素class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap(); for (int i = 0; i < nums.length; i++) { int res = target - nums[i]; if (map.containsKey(res)) { return new int[] {map.get(res), i}; } map.put(nums[i], i); } return null; } }