[Swift] Two Sum

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

聽說是經典Amazon 的面試題。沒想到這次居然碰到，解法很多，最最簡單就是brute-force暴力解法，但是效率最差 O(n 2 )  。好一點就是用hashing的方式，時間複雜度 O(n)

我覺得開始前要先確定一些問題:

• Are the array elements necessarily positive or could be negative or zero?
• Can the array contain duplicates?
• Is the array is sorted?
• Can we consider pairs of an element and itself? [2,4] 和 [4,2] 是為相同還是相異?

如果允許有duplicates 的情況，我的想法是用一個dictionary去存每個數字發生的次數，然後每次把可以配對的數字找出來後就把次數減一。如果沒有duplicates的情況的話就很簡單了，直接用Set 去處理就可以了。