给定一个数字数组,找出其中是否有3个数相加等于0。
使用N^2的时间复杂度,如何实现这个功能?
给定一个数字数组,找出其中是否有3个数相加等于0。
使用N^2的时间复杂度,如何实现这个功能?
这是一个没有使用哈希表的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的解决方案编写的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
将每个数字的负数放入哈希表或其他常量时间查找数据结构中。(n)
循环遍历数组,获取每组两个数字(n^2),并检查它们的和是否在哈希表中。
#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;
}
首先对数组进行排序,然后对于数组中的每个负数(A),在数组中找到两个元素使它们相加等于-A。在排序后的数组中找到两个元素使它们相加等于给定数字需要O(n)时间,因此整个时间复杂度为O(n^2)。
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;
}
这是我使用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
}
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