程式練功房 - LeetCode 1. Two Sum－學海無涯，很深，非常恩咕嚕咕嚕咕嚕

Leetcoode其實一直有在寫，只是每次寫了過一段時間又會覺得不踏實，藉此乾脆弄一個部落格，把解題的心得與過程記錄下來以備不時之需

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

養成好的習慣，在寫程式前先寫好測試單元。

簡單的寫了一個struct來讓測試比較好運行

struct TestData {
   std::vector<int> ques; // 欲尋找的陣列，如上述的Example的話就是 [2, 7, 11, 15 ]
   int target;
   std::vector<int> ans; // 預期答案
};

設計了幾個測試case如下:

一般功能的測試: { { 2,7,11,0,10 }, 9, { 0,1 } }
target為負的情況: { { -2,-7,11,0,-3,10 }, -10, { 1, 4 } }
欲查詢的陣列需要相同的元素來組成目標時{ { 2,7,11,0,10,0 }, 0, { 3,5 } }
tartget需要正負的兩個元素所組成{ { -2,7,11,0,1,10 }, -1, { 0,4 } }

運行單元測試的內容如下:


int main(){	
	// 單元測試集合
	std::vector TestSet = {
		{ { 2,7,11,0,10 },9,{ 0,1 } },
		{ { -2,-7,11,0,-3,10 },-10,{ 1, 4 } },
		{ { 2,7,11,0,10,0 },0,{ 3,5 } },
		{ { -2,7,11,0,1,10 },-1,{ 0,4 } }
	};

	Solution s;
	// 尋遍各個測試單元並驗證是否相同
	for (int32_t i = 0; i < TestSet.size(); i++) {
		if (TestSet[i].ans != s.twoSum(TestSet[i].ques, TestSet[i].target)) {
			return false;
		}
	}
    return true;
}

直覺的解題邏輯與步驟是，

尋遍欲查詢的陣列並做下面這件事情
將target 減去當前元素的值
查找陣列中是否有與減去後相同的元素
若有則返回當前元素與找到的元素索引


class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::vector<int>::iterator it;
        
        // 尋遍整個陣列
        for (int i = 0; i < nums.size(); i++) {

            // 查找target - 當前元素值並使用find來尋找相同元素
            it = find(nums.begin(), nums.end(), target - nums[i]);

            // 如果有則返回
            if (it != nums.end()) {  
                std::vector<int> ans;
               
               // 當前的索引
                ans.push_back(i);

               // 找到的另一個索引
                ptrdiff_t pos = it - nums.begin();
                ans.push_back(pos);
                return ans;
            }
        }
    }
};

第一次的寫出來的解法如下

但在執行測試單元後就會發現在第三個測試單元中就會失敗

3.欲查詢的陣列需要相同的元素來組成目標時{ { 2,7,11,0,10,0 }, 0, { 3,5 } }他回傳了{3, 3 }這個答案 ( 幸好有寫單元測試)

那麼將答案改過之後變成


class Solution {
public:
    std::vector twoSum(std::vector& nums, int target) {
        std::vector::iterator it;
        
        // 尋遍整個陣列
        for (int i = 0; i < nums.size(); i++) {

            // 查找target - 當前元素值並使用find來尋找相同元素
            it = find(nums.begin() + i + 1, nums.end(), target - nums[i]);

            // 如果有則返回
            if (it != nums.end()) {  
                std::vector ans;
               
               // 當前的索引
                ans.push_back(i);

               // 找到的另一個索引
                ptrdiff_t pos = it - nums.begin();
                ans.push_back(pos);
                return ans;
            }
        }
    }
};

測試單元都有通過了，那麼把答案提交看看吧!因該還有進步的空間。

果然沒猜錯，在執行速率上被一堆人打趴!果然功力還有差。

經過一個小時的苦思，有想到一個降低時間複雜度的方式。

基本的思路是「將查找的動作換成hash table」:

步驟大致如下:

1.先用一個迴圈建立hash_table

但在第三個測試項目中產生衝突:

因為是用迴圈建立的，所以如果KEY發生衝突會以最後一個相同的KEY找到的元素為value

雖然在這個題目上應該是沒有問題的，待會再來處理這個情況。

2.利用target-當前元素去查找

所以經過修改後解答變成這樣


class Solution {
public:
    vector twoSum(vector& nums, int target) {   
		std::map m;
		for (int i = 0; i < nums.size(); i++) {
			m[nums[i]] = i;
		}
		std::map::iterator it;
		for (int i = 0; i < nums.size(); i++) {
			it=m.find(target - nums[i]);
			if (it != m.end() && it->second!=i) {
				std::vector ans = { i, it->second};
				return ans;
			}
		}
    }
};

好那麼將答案提交看看

OK! 果然有顯著的提升，但還是有進步的空間。

好的，看看還有什麼地方可以加快的，

「是不是可以把兩個迴圈寫成一個!!??」


class Solution {
public:
    vector twoSum(vector& nums, int target) {   
		std::map m;
		std::map::iterator it;
		for (int i = 0; i < nums.size(); i++) {
			it = m.find(target - nums[i]);
			if (it != m.end() && it->second != i) {
				std::vector ans = { it->second ,i};
				return ans;
			}
			m[nums[i]] = i;
		}
    }
};

這樣應該是最快了吧!!

興奮的提交答案後