1.Two Sum

【题目】

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the_same_element twice.

給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重複利用。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

【思路】

這邊一開始就先想到用兩個迴圈去跑對應，

但考慮到時間複雜度比較高，所以第二個方法就是用Map去比對

把每一個結果去比對Map內的Key，如果有Mapping就表示答案正確。

【解法】

☆JAVA

public class Solution {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer , Integer> map = new HashMap<Integer,Integer>();      //建立HashMap
        for(int i = 0 ; i < nums.length ; i++) {
            int targetTemp = target - nums[i];                            //計算TargetTemp
            if(map.containsKey(targetTemp)) {                             //比對Map
                return new int[] { map.get(targetTemp) , i};              //如果比對成功表示相加等同Target
            }
            map.put(nums[i], i);                                          //如果比對失敗即存入Map內，後續使用
        }
    throw new IllegalArgumentException("No solution , Sorry!");
    }
}

☆Python

class Solution:
    def twoSum(self, nums, target):    
    dict = {};                                    #建立Dict
    list = [];
    for x in range(len(nums)):
        targetTemp = nums[x];                                        
        key = target - targetTemp;                #計算TargetTemp
        if(key in dict):# key in nums = find key  #比對Dict
            list.append(dict[key]);               #如果比對成功表示相加等同Target
            list.append(x);
            return list
        else:
            dict[targetTemp] = x;                 #如果比對失敗即存入Dict內，後續使用