leetcode 1 Two Sums

Seawolf

暴力解法：

1. class Solution {
   
2.     public int[] twoSum(int[] nums, int target) {
   
3.         
   
4.         int len = nums.length;
   
5.         
   
6.         int i,j;
   
7.         
   
8.         int[] array = {-1,-1};
   
9.         
   
10.         for(i = 0 ; i < len-1; i++){
    
11.             
    
12.             for(j = i+1; j < len ;j++){
    
13.                
    
14.                 if(nums[i] + nums[j] == target){
    
15.                
    
16.                     array[0] = I;
    
17. 
    
18.                     array[1] = j;
    
19. 
    
20.                     return array;
    
21.                 }
    
22.             }
    
23.         }
    
24.         
    
25.         return null;
    
26.     }
    
27. }

复制代码

两个for loop，running time O(n^2)

引入hashmap 对算法进行改进：

1. class Solution {
   
2.    
   
3.     public int[] twoSum(int[] nums, int target) {
   
4. 
   
5.         Map<Integer, Integer> map = new HashMap<>();
   
6.         
   
7.         for(int i = 0; i < nums.length; i++) {
   
8. 
   
9.             if(map.get(nums[i]) != null) {
   
10. 
    
11.                 int res[] = {map.get(nums[i]), I};
    
12. 
    
13.                 return res;
    
14. 
    
15.             }
    
16. 
    
17.             map.put(target - nums[i], i);
    
18.         }
    
19.         
    
20.         return new int[]{};
    
21.     }
    
22. }

复制代码

running time 提高到 O(n)