本篇同步發布於Blog:[解題] LeetCode - 1 Two Sum

平台：

LeetCode

題號：

1 - Two Sum

題目連結：

https://leetcode.com/problems/two-sum/

題目說明：

        LeetCode經典題目，輸入1個陣列nums和一個目標和target，求找到nums的2個元素相加會等於target的索引值。題目確保一定只有一個解，且回傳索引的順序沒差異。

比如範例輸入的nums = [2,7,11,15], target = 9，相加變成9的只有2和7，所以回傳這2個元素的索引值[0, 1]。

解題方法：

   　 如果考慮暴力法，需要用雙層迴圈找所有的組合，需要花O(n2)。

更好的設計方法，是用一個HashMap記錄缺少的那一個值(target - nums[i])和對應的索引。

稍微改變範例輸入，nums = [2,11, 7,15]：

1. nums[0]是2，在HashMap[2]不存在，於是建立HashMap[9 - 2 = 7] = 0
2. nums[1]是11，在HashMap[11]不存在，於是建立HashMap[9 - 11 = -2] = 1
3. nums[2]是7，在HashMap[7]存在，於是回傳[2,  HashMap[7]] = [2, 0]

由於是用沒有排序的HashMap，寫值和讀值都是O(1)，整體時間需要O(n)

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> repeat;
        vector<int> ans;
        for(int i = 0;i < nums.size();++i){
            if(repeat.count(nums[i])){
                ans.push_back(repeat[nums[i]]);
                ans.push_back(i);
                break;
            }
            repeat[target - nums[i]] = i;
        }
        
        return ans;
    }
};

int main() {
	vector<int> nums{2,7,11,15};
	Solution sol;
	vector<int> ans = sol.twoSum(nums, 9);
	for(int num : ans){
		cout << num << " ";
	}
	return 0;
}
@u8989332
 

using System;
using System.Collections.Generic;

namespace LeetCode1
{
	public class Solution {
	    public int[] TwoSum(int[] nums, int target) {
	        Dictionary<int, int> repeat = new Dictionary<int, int>();
	        int[] ans = new int[2];
	        for(int i = 0;i < nums.Length;++i){
	            if(repeat.ContainsKey(nums[i])){
	                ans[0] = repeat[nums[i]];
	                ans[1] = i;
	                break;
	            }
	            repeat[target - nums[i]] = i;
	        }
	        
	        return ans;
	    }
	}
	
	public class Program
	{
	
		public static void Main()
		{
			int[] nums = new int[]{2,7,11,15};
			Solution sol = new Solution();
			int[] ans = sol.TwoSum(nums, 9);
			foreach(int num in ans)
			{
				Console.Write(num + " ");
			}
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/1-99/1.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/1-99/1.cs