- 题目
- 暴力破解
- HashMap空间换时间
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
链接：https://leetcode-cn.com/problems/two-sum/
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] nums[1] = 2 7 = 9 所以返回 [0, 1]
暴力破解
两层for循环，针对每一个数 n，遍历里面是否有另外一个数为target-n。时间复杂度为 O(n2) ，空间复杂度为O(1)。
public int[] twoSum2(int[] nums, int target) {
int []result = new int[2];
for(int i=0;i<nums.length-1;i ){
for(int j=1;i j<nums.length;j ){
if(nums[i] nums[i j]==target){
result[0]=i;
result[1]=i j;
}
}
}
return result;
}
HashMap空间换时间
借助hashmap，key为元素的值，value为元素的下标,将数字不断放进hashmap，放之前判断里面是否存在target-num
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
if (nums == null || nums.length == 0) {
return result;
}
Map<Integer, Integer> numSet = new HashMap<>();
for (int i = 0; i < nums.length; i ) {
if (numSet.containsKey(target - nums[i])) {
result[0] = numSet.get(target - nums[i]);
result[1] = i;
return result;
} else {
numSet.put(nums[i], i);
}
}
return result;
}
复杂度分析：
- 时间复杂度：O(N)，遍历了所有的数。
- 空间复杂度：O(N)，hashMap的大小最大为n。
【作者简介】： 秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。这个世界希望一切都很快，更快，但是我希望自己能走好每一步，写好每一篇文章，期待和你们一起交流。
此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~
