2019年7月19日 - 1

时间：2021-09-20 22:23:41

https://leetcode-cn.com/problems/two-sum/

 

2019年7月19日 - 1

我的方法:

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int[] ans = new int[2];
 4         for(int i=0;i<nums.length;++i){
 5             for(int j=i+1;j<nums.length;++j){
 6                 if(nums[i] + nums[j] == target){
 7                     ans[0] = i;
 8                     ans[1] = j;
 9                 }
10             }
11         }
12         return ans;
13     }
14 }

没啥好说的,暴力找就完事.

时间复杂度O(n2),空间复杂度O(1)

 

学到的方法:

利用Hash表,空间换时间

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int[] ans = new int[2];
 4         HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
 5         for(int i=0;i<nums.length;++i){
 6             if(map.containsKey(target - nums[i])){
 7                 ans[0] = map.get(target - nums[i]);
 8                 ans[1] = i;
 9                 break;
10             }else{
11                 map.put(nums[i],i);
12             }
13         }
14         return ans;
15     }
16 }

时间复杂度O(n),空间复杂度O(n)

//存疑,有大佬说containsKey内部也有循环,时间复杂度应该不是真的O(n),应当介于O(n)到O(n2)间

标签：