原創(chuàng)：悅樂(lè)書 程序員小川

給定一個(gè)整數(shù)數(shù)組，找出其中兩個(gè)數(shù)相加等于目標(biāo)值

例如：給定數(shù)組及目標(biāo)值 nums = [2,7,11,15] ,target = 9
因?yàn)閚ums[0] + nums[1] = 2 + 7 = 9
返回[0,1]
利用HashMap

解法一：

這道題目求的是數(shù)組內(nèi)任意兩元素之和等于給定的目標(biāo)整數(shù)，于是很容易想到數(shù)組for循環(huán)遍歷，并且是兩層for循環(huán)，于是第一版的代碼思路已經(jīng)有了。

//java代碼實(shí)現(xiàn)
private int[] findData(int[] array,int target){
   int[] result={-1,-1};
   HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
   for(int i=0;i<array.length;i++){
      map.put(array[i],i); 
     }

 for(int i=0;i<array.length;i++){
      int two = target-array[i];
     if(map.containKey(two)&&target!=2*two){
          result[0]=i;
         result[1]=map.get(two);
         break;
   }
 }
 retrurn result;
}

//Kotlin代碼實(shí)現(xiàn)
fun twoSum1(nums: IntArray, target: Int): IntArray? {
            var result = IntArray(2)
            if (nums.size < 2)
                return null
            for (i in 0..nums.size-1) {
                for (j in i + 1..nums.size-1) {
                    if (nums[i] + nums[j] == target) {
                        result[0] = nums[i]
                        result[1] = nums[j]
                    }
                }
            }
            return result;
        }

解法二：

上面的解法是兩層循環(huán)，循環(huán)次數(shù)是n*(n-1)次，n為數(shù)組元素個(gè)數(shù)，n越大，程序執(zhí)行的時(shí)間越長(zhǎng)，那能不能只循環(huán)一次？既然可以做加法匹配，那做減法呢？先拿到目標(biāo)整數(shù)與數(shù)組中每位元素的差值，再去判斷此差值是否存在于此數(shù)組中。這時(shí)，我們需要一個(gè)存新數(shù)據(jù)的集合，既包含每位元素，也包含每位元素的索引，對(duì)此選取Map作為存放新數(shù)據(jù)的對(duì)象。

 //java實(shí)現(xiàn)
 public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] result=new int[2];
        for(int i=0;i<nums.length;i++){
            int value = target-nums[i];
            if(map.containsKey(value))
            {
               result[0]=i;
               result[1]=map.get(value);
                break;
            }          
            map.put(nums[i],i);
        }
        return result;
        
    }

//Kotlin實(shí)現(xiàn)
 fun twoSum2(nums: IntArray, target: Int): IntArray? {
            var result = IntArray(2)
            if (nums.size < 2)
                return null
            var map = HashMap<Int, Int>()
            for (i in 0..nums.size-1) {
                val k = target - nums[i]
                if (map.containsKey(k)) {
                    result[0] = nums[map.get(k)!!]
                    result[1] = nums[i]
                    break
                }
                map.put(nums[i], i)
            }
            return result
        }