Leetcode - 1. Two Sum

Leetcode - Two sum problems has several approaches. first one is O(n^2) time complexity with two for loops. I'll not cover that approach in this post.

1 O(n log\_n) approach

1 sorting arrays. remind that origin index should be remained.
2 using two pointers, if sum value is same with target value then return it.
3 if sum value is larger than target value, then decrease tail pointer. If in opposite situation, then increase head pointer.

following code is written in JavaScript

const twoSum = (nums, target) => {
  const nums_with_idx = [...nums].map((i, idx) => [i, idx]);
  const sorted = nums_with_idx.sort((a, b) => a[0] - b[0]);
  let i = 0;
  let j = sorted.length - 1;
  while (i < j) {
    const sum = sorted[i][0] + sorted[j][0];
    if (sum == target) return [sorted[i][1], sorted[j][1]];
    if (sum > target) j--;
    else i++;
  }
  return [];
};

2 O(n) ~ O(n log n) approach

1 While iterating arrays, find matching element that makes sum with current value equals target value.
2 If couldn't find matched element, then assign item in dictionary(hash) with index.

Notice. time complexity is depends on implementation of hash data structure. O(n) ~ O(n log n)/remind c++ has Map that consume O( log n ) in a operation - STL Map based on Red black tree

following code is written in Python

class Solution(object):
    def twoSum(self, nums, target):
        d:dict = {}
        res = None
        for i in range(0, len(nums)): 
            cur = nums[i]
            if d.get(target - cur) is not None: res = [d[target-cur], i]
            d[cur] = i
            if res: break
        return res

Thanke you.