LeetCode之Two Sum

1、題目

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].      

2、代碼實作

方法1:

通過2層循環解決，相當于把每個情況都便利出來，看是否有符合要求的沒？代碼如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        if (nums.empty() || (nums.size() == 0))
            return result;
        for (int i = 0; i < nums.size() ; ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                 if (nums[i] + nums[j] == target) {
                     result.push_back(i);
                     result.push_back(j);
                     return result;
                 }   
            }
        }
        return result;
    }
};      

你看上面不是說了嘛？you may not use the same element twice，特麼我還i < nums.size(),如果i = nums.size() - 1, j =  nums.size() -1這個時候恰好等于target的話，i == j,是自己沒有注意，以後不要忘記，雖然通過程式了，但是呢？時間複雜度O(n*n),如果給我們的數組都是正數的沒有順序的，是以我麼可以限制一些元素循環，比如if(ums[i] > target) continue,修改代碼如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        if (nums.empty() || (nums.size() == 0))
            return result;
        for (int i = 0; i < nums.size() － 1; ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                 if (nums[i] > target) 
                     continue;
                 if (nums[i] + nums[j] == target) {
                     result.push_back(i);
                     result.push_back(j);
                     return result;
                 }   
            }
        }
        return result;
    }
};      

方法2:

既然是從一個數組裡面找到2個正确資料和為目标資料，我們用逆向思維，用目标數減去一個正确資料，那麼差就是另外一個正确資料，如果減去的不是正确的資料，那結果肯定也不是正确的資料，我們可以把所有的資料裝在hashmap裡面，key為資料，value為下标，周遊每個資料，如果目标資料減去每個周遊的資料的差是hashmap裡面的key,就可以了，我們可以得到value,也就是index.這樣時間複雜度降低了，變成了O(n)

代碼如下：

//import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (null == nums)
            return null;       
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            Integer value = map.get(nums[i]);
            if (null == value) 
                map.put(nums[i], i);
            Integer index = map.get(target - nums[i]);
            if (null != index && index < i)
            {
                result[0] = index;
                result[1] = i;
            }
        }
        return result;
    }  
}      

這裡為什麼不把 下标設定成key，nums[i]設定成value呢？如果這樣設定的話，我們每次put(i, nums[i]),我們target - nums[i]得到另外一個正确的值，但是我們程式需要的下表，我需要通過正确的nums[i],的到i,也就 是說通過value的到key,得不到吧，是以請注意，反過來就可以了。

特麼我這麼寫還通過不了,下面就不寫判斷條件了，

import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        int[] result = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            Integer values = Integer.valueOf(nums[i]);
            if (!map.containkey(values))
                map.put(i, nums[i]);
            Integer index = map.get(target - nums[i]);
            if (null != index && index < i)
            {
                result[0] = index;
                result[1] = i;
            }
        }
        return result;
    }
    
}      

提示出現：

Line 9: error: cannot find symbol: method containkey(Integer)

明天eclipse跑下，日了狗

C＋＋實作代碼如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        if (nums.size() == 0 || nums.empty())
            return result;
        map<int, int> map;
        for (int i = 0; i < nums.size(); ++i) {
            if (!map.count(nums[i])) {  //特麼我這裡忘記寫！，日了狗
                map.insert(pair<int, int>(nums[i], i));
            }
            if (map.count(target - nums[i])) {  //這裡自己傻逼了，寫成map[target - nums[i]]了
                int index = map[target - nums[i]];
                if (index < i) {
                    result.push_back(index);
                    result.push_back(i);
                    return result;
                }
            }
        }
        return result;
    }
};      

3、總結

1、寫代碼的時候要注意，如果有2個下标的話，第二個大需要j = i + 1,這樣就永遠大了，然後就是i 和 j不相等的話，注意i < nuns[i].size() - 1,不是i < nuns[i].size()，不這樣的話i和j有可能就相等了。

2、我們為了降低時間複雜度，我們可以逆向思路，既然2個數加起來為目标數，那麼目标數減去一個正确的資料，另外肯定是一個正确的資料，就可以通過map資料結構得到下标，

3、我們寫代碼的時候，一定要注意if(!map.count(nums[i])),不要寫成了if(map.count(nuts[i])),不要忘記了!.

4、熟悉了C++的map用法和count函數是否包含key的作用。