测试 加上注释

crossoverJie · crossoverJie · commit 7bd21721f993 · 2018-01-04T11:17:21.000+08:00
diff --git a/src/main/java/com/crossoverjie/algorithm/TwoSum.java b/src/main/java/com/crossoverjie/algorithm/TwoSum.java
@@ -1,5 +1,8 @@
 package com.crossoverjie.algorithm;
 
+import java.util.HashMap;
+import java.util.Map;
+
 /**
  * Function:
  *
@@ -9,6 +12,12 @@
  */
 public class TwoSum {
 
+    /**
+     * 时间复杂度为 O(N^2)
+     * @param nums
+     * @param target
+     * @return
+     */
     public int[] getTwo1(int[] nums,int target){
         int[] result = new int[2] ;
 
@@ -24,4 +33,28 @@ public int[] getTwo1(int[] nums,int target){
         }
         return result ;
     }
+
+
+    /**
+     * 时间复杂度 O(N)
+     * 利用Map Key存放目标值和当前值的差值，value 就是当前的下标
+     * 每次遍历是 查看当前遍历的值是否等于差值，如果是等于，说明两次相加就等于目标值。
+     * 然后取出 map 中 value ，和本次遍历的下标，就是两个下标值相加等于目标值了。
+     *
+     * @param nums
+     * @param target
+     * @return
+     */
+    public int[] getTwo2(int[] nums,int target){
+        int[] result = new int[2] ;
+        Map<Integer,Integer> map = new HashMap<>(2) ;
+        for (int i=0 ;i<nums.length;i++){
+
+            if (map.containsKey(nums[i])){
+                result = new int[]{map.get(nums[i]),i} ;
+            }
+            map.put(target - nums[i],i) ;
+        }
+        return result ;
+    }
 }
diff --git a/src/test/java/com/crossoverjie/algorithm/TwoSumTest.java b/src/test/java/com/crossoverjie/algorithm/TwoSumTest.java
@@ -13,4 +13,13 @@ public void getTwo1() throws Exception {
 
     }
 
+    @Test
+    public void getTwo2(){
+        TwoSum twoSum = new TwoSum() ;
+        int[] nums ={1,3,5,7};
+        int[] two = twoSum.getTwo2(nums, 4);
+        System.out.println(JSON.toJSONString(two));
+
+    }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -13,4 +13,13 @@ public void getTwo1() throws Exception {`
`13`	`13`
`14`	`14`	`}`
`15`	`15`
	`16`	`+ @Test`
	`17`	`+ public void getTwo2(){`
	`18`	`+ TwoSum twoSum = new TwoSum() ;`
	`19`	`+ int[] nums ={1,3,5,7};`
	`20`	`+ int[] two = twoSum.getTwo2(nums, 4);`
	`21`	`+ System.out.println(JSON.toJSONString(two));`
	`22`	`+`
	`23`	`+ }`
	`24`	`+`
`16`	`25`	`}`