第十八题：四数之和

2024-09-07 12:04

文章标签 四数第十八

本文主要是介绍第十八题：四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，找出 nums 中的四个整数，使得它们的和等于 target。你可以假设每个输入都只有一个解决方案，并且不能使用同一个元素多次。

实现思路

采用排序加双指针的方法来解决这个问题。首先对数组进行排序，然后遍历数组，对于每一个元素，设定一个新的目标值为原目标值减去这个元素的值，再利用三数之和的解法找到剩下的三个数。为了避免重复，在遍历过程中需要跳过与前一元素相同的元素。

算法实现

C

#include <stdio.h>
#include <stdlib.h>int cmp(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}void fourSumUtil(int *nums, int numsSize, int start, int end, int target, int *result, int index) {if (start >= end) return;for (int i = start; i < end; ++i) {if (i > start && nums[i] == nums[i-1]) continue;int newTarget = target - nums[i];for (int j = i + 1; j < end; ++j) {if (j > i + 1 && nums[j] == nums[j-1]) continue;int left = j + 1;int right = end - 1;while (left < right) {int sum = nums[j] + nums[left] + nums[right];if (sum == newTarget) {result[index++] = nums[i];result[index++] = nums[j];result[index++] = nums[left];result[index++] = nums[right];++left;--right;while(left < right && nums[left] == nums[left-1]) ++left;while(left < right && nums[right] == nums[right+1]) --right;} else if (sum < newTarget) {++left;} else {--right;}}}}
}int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){qsort(nums, numsSize, sizeof(int), cmp);int resultCount = 0;int **results = malloc(sizeof(int*) * numsSize);int *tempResult = malloc(sizeof(int) * 4 * numsSize);for (int i = 0; i < numsSize; ++i) {if (i == 0 || nums[i] != nums[i-1]) {fourSumUtil(nums, numsSize, i + 1, numsSize, target, tempResult, resultCount);int currentResultIndex = resultCount;while(resultCount % 4 != 0) {results[currentResultIndex / 4] = &tempResult[currentResultIndex];++currentResultIndex;}}}*returnSize = resultCount / 4;*returnColumnSizes = malloc(sizeof(int) * (*returnSize));for(int i = 0; i < (*returnSize); ++i) {(*returnColumnSizes)[i] = 4;}free(tempResult);return results;
}

Python

def fourSum(nums, target):nums.sort()result = []quadruplets = []for i in range(len(nums)-3):if i > 0 and nums[i] == nums[i-1]:continuefor j in range(i+1, len(nums)-2):if j > i+1 and nums[j] == nums[j-1]:continuel, r = j+1, len(nums)-1while l < r:total = nums[i] + nums[j] + nums[l] + nums[r]if total < target:l += 1elif total > target:r -= 1else:result.append([nums[i], nums[j], nums[l], nums[r]])while l < r and nums[l] == nums[l+1]:l += 1while l < r and nums[r] == nums[r-1]:r -= 1l += 1r -= 1return result

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> results = new ArrayList<>();for (int i = 0; i < nums.length - 3; i++) {if (i != 0 && nums[i] == nums[i - 1]) continue;for (int j = i + 1; j < nums.length - 2; j++) {if (j != i + 1 && nums[j] == nums[j - 1]) continue;int left = j + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum < target) {left++;} else if (sum > target) {right--;} else {results.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}}return results;}
}