四数之和

题目

提示:

• 1 <= nums.length <= 200
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹

示例

输入: nums = [1, 0, -1, 0, -2, 2], target = 0

输出: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0 ,2]]

题解

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b)
  const result = []
  const n = nums.length

  for (let a = 0; a < n - 3; a++) {
    // Skip duplicate values for a
    if (a > 0 && nums[a] === nums[a - 1]) continue

    for (let b = a + 1; b < n - 2; b++) {
      // Skip duplicate values for b
      if (b > a + 1 && nums[b] === nums[b - 1]) continue

      let c = b + 1
      let d = n - 1

      while (c < d) {
        const sum = nums[a] + nums[b] + nums[c] + nums[d]

        if (sum === target) {
          // Found a quadruplet
          result.push([nums[a], nums[b], nums[c], nums[d]])

          // Skip duplicate values for c and d
          while (c < d && nums[c] === nums[c + 1]) c++
          while (c < d && nums[d] === nums[d - 1]) d--

          c++
          d--
        } else if (sum < target) {
          c++
        } else {
          d--
        }
      }
    }
  }

  return result
}

Rust

pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let n = nums.len();
    let mut nums = nums;
    nums.sort();
    let mut result: Vec<Vec<i32>> = vec![];

    // `1 <= nums.len() <= 200`, return empty vec in case overflow.
    if n < 4 {
        return result;
    }

    for a in 0..(n - 3) {
        if a > 0 && nums[a] == nums[a - 1] {
            continue;
        }

        for b in (a + 1)..(n - 2) {
            if b > a + 1 && nums[b] == nums[b - 1] {
                continue;
            }

            let mut c = b + 1;
            let mut d = n - 1;

            while c < d {
              // sum maybe grater than i32::MAX
                let sum: i64 = nums[a] as i64 + nums[b] as i64 + nums[c] as i64 + nums[d] as i64;

                if sum > i32::MAX as i64 {
                    c += 1;
                    d -= 1;
                    continue;
                }

                if sum < target as i64 {
                    c += 1;
                }

                if sum > target as i64 {
                    d -= 1;
                }

                if sum == target as i64 {
                    result.push(vec![nums[a], nums[b], nums[c], nums[d]]);

                    while c < d && nums[c] == nums[c + 1] {
                        c += 1;
                    }
                    while c < d && nums[d] == nums[d - 1] {
                        d -= 1;
                    }

                    c += 1;
                    d -= 1;
                }
            }
        }
    }

    result
}