Hey Team,
I wrote some working Swift code! (Yay!)
My investigation into building and using a HASH TABLE in Swift brought me here :
But that looks like a heckin’ of a lot of work and was written six years ago.
The approach I took was to use the fact that Dictionary conforms to Hashable and therefore can function as a Hash Table. (Am I right about this?)
So, please find my proposed solution below for your critical review.
It works, but is this the BEST or MOST APPROPRIATE way to do this?
(Java and Python3 solutions are presented for reference.)
Thank you for your time and attention.
// Project : Code Interview Problems and Solutions (CIPS)
//
// Problem : Two Sum
//
// Difficulty : Easy
//
// Given an array of integers nums and an integer target,
// return indices of the two numbers such that they add up to target.
//
// You may assume that each input would have exactly one solution,
// and you may not use the same element twice.
//
// You can return the answer in any order.
//
// Example 1:
//
// Input: nums = [2,7,11,15], target = 9
// Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
//
// Example 2:
//
// Input: nums = [3,2,4], target = 6
// Output: [1,2]
//
// Example 3:
//
// Input: nums = [3,3], target = 6
// Output: [0,1]
//
// Constraints:
//
// 2 <= nums.length <= 10^4
// -10^9 <= nums[i] <= 10^9
// -10^9 <= target <= 10^9
// Only one valid answer exists.
//
// Follow-up:
//
// Can you come up with an algorithm that is less than O(n^2) time complexity?
//
// Approach : One Pass Hash Table
//
// Algorithm
//
// Iterate through nums.
// Put nums-values and nums-indices into hash table.
// Check if current nums-value's complement is in hash table.
// If found, return solution
//
// Java Code
//
// class Solution {
// public int[] twoSum(int[] nums, int target) {
// Map<Integer, Integer> map = new HashMap<>();
// for (int i = 0; i < nums.length; i++) {
// int complement = target - nums[i];
// if (map.containsKey(complement)) {
// return new int[] { map.get(complement), i};
// }
// map.put(nums[i], i);
// }
// // If no solution, return null
// return null;
// }
//
// Python3 Code
//
// class Solution:
// def twoSum(self, nums: List[int], target: int) -> List[int]:
// hashmap = {}
// for i in range(len(nums)):
// complement = target - nums[i]
// if complement in hashmap:
// return [i, hashmap[complement]]
// hashmap[nums[i]] = i
//
// Swift Code
//
// Note: Dictionary conforms to Hashable and performs as a hash table.
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict: Dictionary<Int, Int> = [:]
for i in 0 ..< nums.count {
let complement:Int = target - nums[i]
var containTest = dict.contains { $0.value == complement }
if containTest {
let key = dict.filter{ $0.value == complement }.keys.first!
return [key, i]
}
dict[i] = nums[i]
}
// If no solution, return nil
var arr = [Int]()
return arr
}
}
var tester = Solution()
// Testcase 1
tester.twoSum([2,7,11,15], 9) // Returns [0, 1]
// Testcase 2
tester.twoSum([3,2,4], 6) // Returns [1, 2]
// Testcase 3
tester.twoSum([3,3], 6) // Returns [0, 1]
// End of problem and solution.
Thanks, again.