力扣题解最佳实践  >  双指针技术  >  18. 四数之和  >  已用 Python, JavaScript, Ruby, Java, C++, Go, C# 语言实现  >  贡献代码 或 转发

    力扣链接：18. 四数之和，难度：中等。

    给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

    • 0 <= a, b, c, d < n
    • a、b、c 和 d 互不相同
    • nums[a] + nums[b] + nums[c] + nums[d] == target

    你可以按 任意顺序 返回答案 。

    示例 1:

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

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

    示例 2:

    输入: nums = [2,2,2,2,2], target = 8

    输出: [[2,2,2,2]]

    约束:

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

    思路
    上一题下一题

    1. 本题思路同15. 三数之和, 请点链接查看。
    2. 区别是三数变四数，处理四数，只需要多加一重嵌套的循环。
    3. 另外增加了target参数，计算时需要把它做为条件带入。
    4. 你可能已经看出来了，不管它是两数、三数还是四数，都可以用双指针技术。

    复杂度

    时间复杂度

    O(N^3)

    空间复杂度

    O(N)

    题解语言： Python JavaScript Ruby Java C++ Go C#

    Python # 

    # If you want the program to run faster, uncomment the two places in the code.
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        # nums_2 = []
        # for i, num in enumerate(nums):
        #     if i >= 4 and num == nums[i - 1] == nums[i - 2] == nums[i - 3] == nums[i - 4]:
        #         continue
        #     nums_2.append(num)
        # nums = nums_2
        results = set()

        for i in range(len(nums) - 3):
            for j in range(i + 1, len(nums) - 2):
                num = nums[i] + nums[j]
                # if num > target / 2:
                #     break
                left = j + 1
                right = len(nums) - 1

                while left < right:
                    sum_ = nums[left] + nums[right]

                    if sum_ == target - num:
                        results.add((nums[i], nums[j], nums[left], nums[right]))
                        left += 1
                    elif sum_ > target - num:
                        right -= 1
                    else:
                        left += 1

        return list(results)

    JavaScript # 

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

  // Uncomment to speed up
  // let nums2 = [];
  // for (let i = 0; i < nums.length; i++) {
  //   if (i >= 4 && nums[i] === nums[i-1] && nums[i-1] === nums[i-2] && nums[i-2] === nums[i-3] && nums[i-3] === nums[i-4]) {
  //     continue;
  //   }
  //   nums2.push(nums[i]);
  // }
  // nums = nums2;

  const results = new Set();

  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      const num = nums[i] + nums[j];
      // Uncomment to speed up
      // if (num > target / 2) {
      //   break;
      // }
      let left = j + 1;
      let right = nums.length - 1;

      while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === target - num) {
          results.add([nums[i], nums[j], nums[left], nums[right]].join(','));
          left++;
        } else if (sum > target - num) {
          right--;
        } else {
          left++;
        }
      }
    }
  }

  return Array.from(results).map(str => str.split(',').map(Number));
};

    Ruby # 

    # @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[][]}
def four_sum(nums, target)
  nums.sort!

  # Uncomment to speed up
  # nums2 = []
  # nums.each_with_index do |num, i|
  #   next if i >= 4 && num == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]
  #   nums2 << num
  # end
  # nums = nums2

  results = Set.new

  (0..nums.length-4).each do |i|
    (i+1..nums.length-3).each do |j|
      num = nums[i] + nums[j]
      # Uncomment to speed up
      # break if num > target / 2
      left = j + 1
      right = nums.length - 1

      while left < right
        sum = nums[left] + nums[right]

        if sum == target - num
          results.add([nums[i], nums[j], nums[left], nums[right]])
          left += 1
        elsif sum > target - num
          right -= 1
        else
          left += 1
        end
      end
    end
  end

  results.to_a
end

    Java # 

    class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> results = new ArrayList<>();

        Arrays.sort(nums);
        Set<List<Integer>> seen = new HashSet<>();

        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum == target) {
                        List<Integer> quadruplet = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        if (!seen.contains(quadruplet)) {
                            results.add(quadruplet);
                            seen.add(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return results;
    }
}

    C++ # 

    class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> results;

        sort(nums.begin(), nums.end());
        set<vector<int>> seen;

        for (int i = 0; i < nums.size() - 3; i++) {
            for (int j = i + 1; j < nums.size() - 2; j++) {
                int left = j + 1;
                int right = nums.size() - 1;

                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum == target) {
                        vector<int> quadruplet = {nums[i], nums[j], nums[left], nums[right]};
                        if (seen.find(quadruplet) == seen.end()) {
                            results.push_back(quadruplet);
                            seen.insert(quadruplet);
                        }
                        left++;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }

        return results;
    }
};

    Go # 

    // If you want the program to run faster, uncomment the two places in the code.

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)

    // nums2 := make([]int, 0)
    // for i := 0; i < len(nums); i++ {
    //     if i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4] {
    //         continue
    //     }
    //     nums2 = append(nums2, nums[i])
    // }
    // nums = nums2

    results := make([][]int, 0)
    seen := make(map[string]bool)

    for i := 0; i < len(nums)-3; i++ {
        for j := i + 1; j < len(nums)-2; j++ {
            num := nums[i] + nums[j]
            // if num > target/2 {
            //     break
            // }
            left := j + 1
            right := len(nums) - 1

            for left < right {
                sum := nums[left] + nums[right]

                if sum == target-num {
                    quadruplet := []int{nums[i], nums[j], nums[left], nums[right]}
                    key := fmt.Sprintf("%d,%d,%d,%d", quadruplet[0], quadruplet[1], quadruplet[2], quadruplet[3])
                    if !seen[key] {
                        results = append(results, quadruplet)
                        seen[key] = true
                    }
                    left++
                } else if sum > target-num {
                    right--
                } else {
                    left++
                }
            }
        }
    }

    return results
}

    C# # 

    // If you want the program to run faster, uncomment the two places in the code.
public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);

        // List<int> nums2 = new List<int>();
        // for (int i = 0; i < nums.Length; i++) {
        //     if (i >= 4 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && nums[i-3] == nums[i-4]) {
        //         continue;
        //     }
        //     nums2.Add(nums[i]);
        // }
        // nums = nums2.ToArray();

        var results = new List<IList<int>>();
        var seen = new HashSet<string>();

        for (int i = 0; i < nums.Length - 3; i++) {
            for (int j = i + 1; j < nums.Length - 2; j++) {
                long num = (long)nums[i] + nums[j];
                // if (num > target / 2) {
                //     break;
                // }
                int left = j + 1;
                int right = nums.Length - 1;

                while (left < right) {
                    long sum = (long)nums[left] + nums[right];

                    if (sum == target - num) {
                        var quadruplet = new[] { nums[i], nums[j], nums[left], nums[right] };
                        string key = string.Join(",", quadruplet);
                        if (!seen.Contains(key)) {
                            results.Add(quadruplet);
                            seen.Add(key);
                        }
                        left++;
                    } else if (sum > target - num) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }

        return results;
    }
}
    题解语言： Python JavaScript Ruby Java C++ Go C#

    其它语言

    欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 18. 四数之和。
    上一题下一题