给定一个数字数组,找出其中3个加起来是否为0

没有哈希表的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。

不是为了信用或其他原因,但这里是我的Python版的CharlesMa的解决方案。很酷。

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),并查看它们的和是否在哈希表中。

首先对数组进行排序,然后对数组中的每个负数(a)查找数组中两个元素,加起来等于-a。在已排序的数组中查找2个元素,加起来等于给定的数字需要O(n)个时间,因此整个时间的复杂性为O(n^2)。

C++实现,基于Charles Ma提供的伪代码,对任何人感兴趣。

#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;
}

这是我在n^2日志n中使用swift 3的方法…

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