1995.统计特殊四元组.md

1995.统计特殊四元组

/*
 * @lc app=leetcode.cn id=1995 lang=typescript
 *
 * [1995] 统计特殊四元组
 */

// @lc code=start
function countQuadruplets(nums: number[]): number {}
// @lc code=end

解法 1: 迭代

function countQuadruplets(nums: number[]): number {
  const n = nums.length
  let res = 0
  for (let i = 0; i < n - 3; i++) {
    for (let j = i + 1; j < n - 2; j++) {
      for (let k = j + 1; k < n - 1; k++) {
        for (let l = k + 1; l < n; l++) {
          if (nums[i] + nums[j] + nums[k] === nums[l]) {
            res++
          }
        }
      }
    }
  }
  return res
}

解法 2: 深度优先搜索

function countQuadruplets(nums: number[]): number {
  let res = 0
  const dfs = (start = 0, depth = 0, sum = 0) => {
    if (start === nums.length) return
    for (let i = start; i < nums.length - (3 - depth); i++) {
      if (depth < 3) {
        dfs(i + 1, depth + 1, sum + nums[i])
      } else if (sum === nums[i]) {
        res++
      }
    }
  }
  dfs()
  return res
}

Case

test.each([
  { input: { nums: [1, 2, 3, 6] }, output: 1 },
  { input: { nums: [3, 3, 6, 4, 5] }, output: 0 },
  { input: { nums: [1, 1, 1, 3, 5] }, output: 4 },
  { input: { nums: [28, 8, 49, 85, 37, 90, 20, 8] }, output: 1 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(countQuadruplets(nums)).toEqual(output)
})