Runtime 105 ms Beats 84.2%

twoSum.ts

function hash_core(num: number, bins: number): number {
    let message: string[] = num.toString().split('');
    let hash: number = 5381;
    message.forEach((e: string) => {
        hash = (hash << 5) + hash + e.charCodeAt(0);
    })
    return Math.abs(hash) % bins;
}

function hash(num: number, bins: number, target: number): number {
  const [a, b] = [num, target - num];
  return a > b ? hash_core(a, bins) : hash_core(b, bins);
}

function check(nums: {'index': number, 'value': number}[], target: number): number[] | null {
  if (nums.length == 1) {
    return null;
  }

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i].value + nums[j].value === target) {
        return [nums[i].index, nums[j].index];
      }
    }
  }

  return null;
  
}


var BINS: number = 8000;
function twoSum(nums: number[], target: number): number[] {
  // construct hash table
  let bins: {'index': number, 'value': number}[][] = [];
  for (let i: number = 0; i < BINS; i++) {
    bins.push([]);
  }

  for (let i = 0, n = nums.length; i < n; i++) {
    const hashed: number = hash(nums[i], BINS, target);
    bins[hashed].push({
      'index': i,
      'value': nums[i]
    });
  
    const checked = check(bins[hashed], target);
    if (checked) {
      return checked;
    }
  }

  return [0, 0];
};