Skip to main content

2 posts tagged with "medium"

View All Tags

15. 3Sum

· 2 min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
function threeSum(input: number[]) {
  const length = input.length;
  input.sort((a, b) => a - b);
  const res = new Set<string>();

  function checkPosition(mid: number) {
    let left = mid - 1;
    let right = mid + 1;

    while (left >= 0 && right < length) {
      const sum = input[left] + input[mid] + input[right];
      if (sum === 0) {
        res.add([input[left], input[mid], input[right]].join(","));
        left--;
      }
      if (sum < 0) {
        right++;
      }
      if (sum > 0) {
        left--;
      }
    }
  }

  for (let i = 1; i < length - 1; i++) {
    checkPosition(i);
  }
  return [...res].map((v) => v.split(","));
}

967. Numbers With Same Consecutive Differences

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Example

Example 1:

Input: n = 3, k = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes. Example 2:

Input: n = 2, k = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Constraints:

2 <= n <= 9 0 <= k <= 9

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
  let results = new Set();
  function travel(arr) {
    if (arr.length === n) {
      results.add(Number(arr.join("")));
    } else if (arr.length < n) {
      const last = arr[arr.length - 1];
      const plus = last + k;
      const minus = last - k;
      if (plus >= 0 && plus <= 9) {
        travel([...arr, plus]);
      }
      if (minus >= 0 && minus <= 9) {
        travel([...arr, minus]);
      }
    }
  }
  for (let i = 1; i < 10; i++) {
    travel([i]);
  }
  return [...results];
};