给定一个数字数组，找出其中是否有3个数相加等于0。
使用N^2的时间复杂度，如何实现这个功能？
给定一个数字数组，找出其中是否有3个数相加等于0。
13
- ryan
4
5提醒一下，这个问题的一般形式被称为“子集和”，如果你想查找更多信息，可以搜索该术语。一般形式是NP完全问题，但如果限制要查找的子集大小为固定值（在此情况下为3），则可解决。 - Tyler McHenry
该数组是否包含负数，还是只有正数？它是否包含零？ - Alex
2这是计算机科学中一个众所周知的问题：http://en.wikipedia.org/wiki/3SUM - user361676
“在数组中找到三个元素的和最接近给定数字”是比这个问题更普遍的版本，但答案是相同的。 - Bernhard Barker
7个回答
40
这是一个没有使用哈希表的O(n^2)解决方案（因为使用哈希表是作弊 :P）。以下是伪代码：
Sort the array // O(nlogn)
for each i from 1 to len(array) - 1
iter = i + 1
rev_iter = len(array) - 1
while iter < rev_iter
tmp = array[iter] + array[rev_iter] + array[i]
if tmp > 0
rev_iter--
else if tmp < 0
iter++
else
return true
return false
基本上使用一个排序好的数组，对于数组中的每个数字（目标），你可以使用两个指针，一个从数组的前面开始，一个从后面开始，检查指针所指向的元素之和是否大于、小于或等于目标，并相应地推进指针，如果找到目标，则返回true。
- Charles Ma
9
len(n) 是数组的长度 :) - Charles Ma
嗨，查尔斯，我还有一个问题。在你的代码中，目标不可能是array [inter]或array [reviter]吗？
那么你就会把相同的数字加两次？ - ryan
@Ryan：我下面写的伪代码（嗯，Python）正是基于此解决了这个问题：它在目标索引的下限增量或上限减量到达时停止。请看“while lower < i < upper:”循环控制。Charles Ma的原始代码只尝试找到第一个匹配实例。我编写的代码可以在提供的整数中找到所有唯一的实例。 - hughdbrown
1哈哈，刚刚发现了一些优化方法，可以解决目标数字与指向数字之一相同的问题 :) - Charles Ma
@Charles Ma：嘿，查尔斯，看看我如何重复使用我的Python代码来回答这个问题：https://dev59.com/hXI_5IYBdhLWcg3wBuRs#1576044 - hughdbrown
显示剩余4条评论
9
这不是为了学分或其他什么，但这是我根据Charles Ma的解决方案编写的Python版本。非常酷。
def find_sum_to_zero(arr):
arr = sorted(arr)
for i, target in enumerate(arr):
lower, upper = 0, len(arr)-1
while lower < i < upper:
tmp = target + arr[lower] + arr[upper]
if tmp > 0:
upper -= 1
elif tmp < 0:
lower += 1
else:
yield arr[lower], target, arr[upper]
lower += 1
upper -= 1
if __name__ == '__main__':
# Get a list of random integers with no duplicates
from random import randint
arr = list(set(randint(-200, 200) for _ in range(50)))
for s in find_sum_to_zero(arr):
print s
远在以后：
def find_sum_to_zero(arr):
limits = 0, len(arr) - 1
arr = sorted(arr)
for i, target in enumerate(arr):
lower, upper = limits
while lower < i < upper:
values = (arr[lower], target, arr[upper])
tmp = sum(values)
if not tmp:
yield values
lower += tmp <= 0
upper -= tmp >= 0
- hughdbrown
1
1如果您需要解释，以下是非Python开发人员的非明显部分：
（1）enumerate返回序列的每个元素及其整数索引，从0开始
（2）“lower < i < upper”表示“lower < i and i < upper”在单个测试中
（3）yield从函数返回一个值，但允许执行从该点继续下一次请求时
（4）set()返回一组唯一的项目，转储多个出现
（5）多个变量可以在单个语句中赋值
（6）生成器语句表示：“在范围-200到200内给我50个整数”。 - hughdbrown
8
将每个数字的负数放入哈希表或其他常量时间查找数据结构中。(n)
循环遍历数组，获取每组两个数字(n^2)，并检查它们的和是否在哈希表中。
- Roland Rabien
3
这个解决方案同样适用于一个稍微不同的问题：
是否存在三/四个数，它们的总和可以被一个常量q整除且没有余数？ - Anna
这个可以运行，但它使用了O(n)的内存，如果我们使用上面提到的其他解决方案之一，就可以避免这种情况。 - tdeegan
如果要使用此解决方案，则需要跟踪您添加到哈希表中的数字的索引，以便在执行n^2循环时避免重复使用相同的数字。 - ralzaul
1
基于Charles Ma提供的伪代码，这是一个C++实现，适用于任何有兴趣的人。
#include <iostream>
using namespace std;
void merge(int originalArray[], int low, int high, int sizeOfOriginalArray){
// Step 4: Merge sorted halves into an auxiliary array
int aux[sizeOfOriginalArray];
int auxArrayIndex, left, right, mid;
auxArrayIndex = low;
mid = (low + high)/2;
right = mid + 1;
left = low;
// choose the smaller of the two values "pointed to" by left, right
// copy that value into auxArray[auxArrayIndex]
// increment either left or right as appropriate
// increment auxArrayIndex
while ((left <= mid) && (right <= high)) {
if (originalArray[left] <= originalArray[right]) {
aux[auxArrayIndex] = originalArray[left];
left++;
auxArrayIndex++;
}else{
aux[auxArrayIndex] = originalArray[right];
right++;
auxArrayIndex++;
}
}
// here when one of the two sorted halves has "run out" of values, but
// there are still some in the other half; copy all the remaining values
// to auxArray
// Note: only 1 of the next 2 loops will actually execute
while (left <= mid) {
aux[auxArrayIndex] = originalArray[left];
left++;
auxArrayIndex++;
}
while (right <= high) {
aux[auxArrayIndex] = originalArray[right];
right++;
auxArrayIndex++;
}
// all values are in auxArray; copy them back into originalArray
int index = low;
while (index <= high) {
originalArray[index] = aux[index];
index++;
}
}
void mergeSortArray(int originalArray[], int low, int high){
int sizeOfOriginalArray = high + 1;
// base case
if (low >= high) {
return;
}
// Step 1: Find the middle of the array (conceptually, divide it in half)
int mid = (low + high)/2;
// Steps 2 and 3: Recursively sort the 2 halves of origianlArray and then merge those
mergeSortArray(originalArray, low, mid);
mergeSortArray(originalArray, mid + 1, high);
merge(originalArray, low, high, sizeOfOriginalArray);
}
//O(n^2) solution without hash tables
//Basically using a sorted array, for each number in an array, you use two pointers, one starting from the number and one starting from the end of the array, check if the sum of the three elements pointed to by the pointers (and the current number) is >, < or == to the targetSum, and advance the pointers accordingly or return true if the targetSum is found.
bool is3SumPossible(int originalArray[], int targetSum, int sizeOfOriginalArray){
int high = sizeOfOriginalArray - 1;
mergeSortArray(originalArray, 0, high);
int temp;
for (int k = 0; k < sizeOfOriginalArray; k++) {
for (int i = k, j = sizeOfOriginalArray-1; i <= j; ) {
temp = originalArray[k] + originalArray[i] + originalArray[j];
if (temp == targetSum) {
return true;
}else if (temp < targetSum){
i++;
}else if (temp > targetSum){
j--;
}
}
}
return false;
}
int main()
{
int arr[] = {2, -5, 10, 9, 8, 7, 3};
int size = sizeof(arr)/sizeof(int);
int targetSum = 5;
//3Sum possible?
bool ans = is3SumPossible(arr, targetSum, size); //size of the array passed as a function parameter because the array itself is passed as a pointer. Hence, it is cummbersome to calculate the size of the array inside is3SumPossible()
if (ans) {
cout<<"Possible";
}else{
cout<<"Not possible";
}
return 0;
}
- totjammykd
1
首先对数组进行排序，然后对于数组中的每个负数（A），在数组中找到两个元素使它们相加等于-A。在排序后的数组中找到两个元素使它们相加等于给定数字需要O(n)时间，因此整个时间复杂度为O(n^2)。
- jianqiang
0
void findTriplets(int arr[], int n)
{
bool found = false;
for (int i=0; i<n-1; i++)
{
unordered_set<int> s;
for (int j=i+1; j<n; j++)
{
int x = -(arr[i] + arr[j]);
if (s.find(x) != s.end())
{
printf("%d %d %d\n", x, arr[i], arr[j]);
found = true;
}
else
s.insert(arr[j]);
}
}
if (found == false)
cout << " No Triplet Found" << endl;
}
- Alexandru Ionescu
0
这是我使用Swift 3的方法，在N ^ 2 log N中...
let integers = [-50,-40, 10, 30, 40, 50, -20, -10, 0, 5]
第一步，排序数组
let sortedArray = integers.sorted()
其次，实现一个二分查找方法，返回索引如下...
func find(value: Int, in array: [Int]) -> Int {
var leftIndex = 0
var rightIndex = array.count - 1
while leftIndex <= rightIndex {
let middleIndex = (leftIndex + rightIndex) / 2
let middleValue = array[middleIndex]
if middleValue == value {
return middleIndex
}
if value < middleValue {
rightIndex = middleIndex - 1
}
if value > middleValue {
leftIndex = middleIndex + 1
}
}
return 0
}
最后，实现一个方法来跟踪每次一组“三元组”相加为0的情况...
func getTimesTripleSumEqualZero(in integers: [Int]) -> Int {
let n = integers.count
var count = 0
//loop the array twice N^2
for i in 0..<n {
for j in (i + 1)..<n {
//Sum the first pair and assign it as a negative value
let twoSum = -(integers[i] + integers[j])
// perform a binary search log N
// it will return the index of the give number
let index = find(value: twoSum, in: integers)
//to avoid duplications we need to do this check by checking the items at correspondingly indexes
if (integers[i] < integers[j] && integers[j] < integers[index]) {
print("\([integers[i], integers[j], integers[index]])")
count += 1
}
}
}
return count
}
print("count:", findTripleSumEqualZeroBinary(in: sortedArray))
打印 --- 数量：7
- James Rochabrun
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接