# CSPT21 Lecture 3
## [Single Number](https://leetcode.com/problems/single-number/)

class Solution:
    """
    [2,2,3,1,3] --> 1
    [1] --> 1
    
    Plan
    Use a dictionary to keep track of how many times an 
    element occurs in the list (element --> numTimesAppeared).
    Iterate through the dictionary, return the element that appears once.
    Runtime: O(n)
    Space: O(n)
    """
    def singleNumber(self, nums: List[int]) -> int:
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1
        for (num, numTimesAppeared) in counts.items():
            if numTimesAppeared == 1:
                return num
        return -1

## [Two Sum](https://leetcode.com/problems/two-sum/)

class Solution:
    """
    Understand
    [3,5,2,1] target = 5
    output = [0, 2]
    
    [2,1] target = 3
    output = [0,1]
    
    Plan
    Approach 1: Runtime O(n^2) Space O(1)
    For each number in nums, look in nums again to see if it has its complement
    
    Approach 2: Runtime O(n) Space O(n)
    Use a dictionary to store the current number --> its index (if it doesn't have a complement). If the current number's complement is in the dictionary then return the indices you're currently at and the index stored in the dictionary
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numsDictionary = {}
        for (i, num) in enumerate(nums):
            if target - num in numsDictionary:
                return [numsDictionary[target - num], i]
            numsDictionary[num] = i
    
    def twoSumApproach1(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]