发现综上所述至K三要素 [英] Finding three elements that sum to K

问题描述

我写了下面找到两个元素的总和设为K

I wrote the following to find two elements that sum to K

#include <iostream>
#include <unordered_map>

void sum_equal_to_k(int *a, int n, int k) { /* O(N) */
    std::unordered_map<int, int> hash;

    // insert all elements in a hash
    for (int i = 0; i < n; i++) {
        hash[a[i]] = 1;
    }

    // print if k - a[i] exists in the hash
    for (int i = 0; i < n; i++) {
        if (hash[k - a[i]] == 1) {
            printf("%d %d\n", a[i], k - a[i]);
        }
    }
}
int main() {
    int a[8] = {3, 5, 2, 1, 6, 7, 4};
    sum_equal_to_k(a, 8, 7);
    return 0;
}

我在这个延伸到3元之麻烦

I'm having trouble extending this to 3-element sum

推荐答案

该问题被称为 3SUM 。这里有一个为O（n ^ 2）算法解决它，你可以找到的此处，不需要任何散列。

The problem is known as 3SUM. There's an O(n^2) algorithm for solving it that you can find here, that doesn't require any hashing.

这将是简单的，如果你只需要使用向量（你已经使用 unordered_map 无论如何，对不对？ ）：

It'll be simpler if you just use vector (you're already using unordered_map anyway, right?):

void sum3_k(std::vector<int> s, int k) {
    std::sort(s.begin(), s.end());

    for (size_t i = 0; i < s.size() - 2; ++i) {
        size_t start = i + 1;
        size_t end = s.size() - 1;

        while (start < end) {
            int sum = s[i] + s[start] + s[end];
            if (sum == k) {
                std::cout << s[i] << " " << s[start] << " " << s[end] << std::endl;
                ++start, --end;
            }
            else if (sum > k) {
                --end;
            }
            else {
                ++start;
            }
        }
    }
}

这篇关于发现综上所述至K三要素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！