LeetCode 1. Two Sum

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Solution

Two Pointers: Search from both sides

Time Complexity: $O(n \log n)$

// Apply the solution for 167. Two Sum II - Input array is sorted here.
// Time Complexity: O(n log n)
//   - Sort values: O(n log n)
//   - Search all values in the array: O(n)
//   => Total: O(n log n + n) = O(n log n)
struct Element {
  int value;
  int index;
  Element(int v, int i)
    : value(v)
    , index(i) {}
  // Overload operator < for std::sort
  bool operator<(const Element& rhs) const { return value < rhs.value; }
};

vector<int> twoSum(vector<int>& nums, int target) {
  vector<Element> elements;
  for(int i = 0 ; i < nums.size() ; ++i) {
    elements.push_back(Element(nums[i], i));
  }

  sort(elements.begin(), elements.end());

  int left = 0;
  int right = elements.size() - 1;
  while (left < right) {
    int sum = elements[left].value + elements[right].value;
    if (sum == target) {
      return vector<int> { elements[left].index, elements[right].index };
    }
    sum < target ? ++left : --right;
  }
  return vector<int> {-1, -1};
}

Hash table

Time Complexity: $O(n)$

// Use HashTable to store every value accessed, 
// so we can search a specific value in O(1) if it's read before.
// Time Complexity: O(n)
//   - Iterate all values in the array: O(n)
//     - Find matched values visited before: O(1)
//   => Total: O(n * 1) = O(n)
vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int, int> valueToIndex;
  for (int i = 0 ; i < nums.size() ; ++i) {
    int toFind = target - nums[i];
    if (valueToIndex.find(toFind) != valueToIndex.end()) {
      return vector<int> {valueToIndex[toFind], i};
    }
    valueToIndex[nums[i]] = i;
  }
  return vector<int> {-1, -1};
}