ac solution code


  • 0

    Solution1. HashMap - time = Add = O(1); Find = O(n); space = O(n)

    The basic idea is:

    1. Use HashMap to count each added unique item: map: [Number: Count]
    2. Find (sum - key) in map.keys:
      1. if key != (sum - key), return true;
      2. if key == (sum - key), means needs two same items, return count > 1
    class TwoSum  {
        private lazy var map = [Int: Int]()
        func add(_ number: Int) {
            map[number] = (map[number] ?? 0) + 1                // Add: increments map[number]
        }
        
        func find(_ sum: Int) -> Bool {
            for key in map.keys {                               // 1. Loop through keys in `map`
                let otherKey = sum - key                        // 2. Check otherKey(sum - key)
                if let count = map[otherKey] {             // 2-0. count = Count of otherKey
                    if key != otherKey ||                       // 2-1. key != otherKey
                       (key == otherKey && count > 1) {    // 2-2. key == otherKey: count > 1
                        return true
                    }
                }
            }
            return false
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.