解題程式碼

var DetectSquares = function () {
  this.points = new Map();
};

/**
 * @param {number[]} point
 * @return {void}
 */
DetectSquares.prototype.add = function (point) {
  this.points.set(`${point[0]}-${point[1]}`, (this.points.get(`${point[0]}-${point[1]}`) || 0) + 1);
};

/**
 * @param {number[]} point
 * @return {number}
 */
DetectSquares.prototype.count = function (point) {
  let count = 0;
  const sameX = [];
  const sameY = [];

  this.points.forEach((value, key) => {
    const [x, y] = key.split('-');

    if (+x === point[0] && +y !== point[1]) sameX.push({ y, value });
    if (+y === point[1] && +x !== point[0]) sameY.push({ x, value });
  });

  for (let i = 0; i < sameX.length; i++) {
    for (let j = 0; j < sameY.length; j++) {
      if (this.points.has(`${sameY[j].x}-${sameX[i].y}`) && Math.abs(sameY[j].x - point[0]) === Math.abs(sameX[i].y - point[1])) {
        count += sameX[i].value * sameY[j].value * this.points.get(`${sameY[j].x}-${sameX[i].y}`);
      }
    }
  }

  return count;
};

解題思路、演算法

簡單來說就是要從已經紀錄的點和查詢的點中找到可以連成正方形的個數，所以要留意做以下的處理:

• 比較兩個點相同時的型別(因為我的解法是把點存成字串，放到 hashMap 當成 key，出現次數則是 value)
• area 為 0 的情況不能算正方形，也就是紀錄的點和查詢的點座標相同
• 找到長方形記得不能算

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料