Leetcode二和

Question

我目前正在从python背景中学习c++，因此我将在python和c++中为以下问题陈述提供一个解决方案：

给定整数、名词和整数目标数组，返回这两个数字的索引，使它们相加为目标。您可以假设每个输入都有一个解决方案，并且可能不会使用相同的元素两次。你可以按任何顺序返回答案。

示例1:

输入:num= 2,7,11,15，target =9

输出：0,1

示例2:

输入:num= 3,2,4，target =6

输出：1,2

我想听听你对性能改进/其他建议的反馈/建议。这是链接

two_sum.py

def two_sum(nums: list, target: int):
    for i, n in enumerate(nums):
        match = target - n
        if match in (rest := nums[i + 1:]):
            match_at = rest.index(match)
            return i, match_at + i + 1


if __name__ == '__main__':
    if result := two_sum([2, 7, 11, 15], 22):
        print(f'Indices:\n{result}')
    else:
        print('No matches found')

Leetcode统计：

运行时: 772 ms，比Python提交的两个Sum快36.98%。内存使用量:14.4MB，不到49.82%的Python在线提交的两个求和。

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;


vector<int> two_sum_solution(vector<int> &nums, int target) {
    vector <int> results;
    for (int i = 0; i < nums.size(); ++i) {
        int match = target - nums[i];
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] == match) {
                for (int index_match : {
                            i, j
                        })
                    results.push_back(index_match);
            }

        }
    }
    return results;
}
#endif //LEETCODE_TWO_SUM_H

main.cpp

#include <vector>
#include "two_sum.h"
using std::vector;


int main() {
    vector<int> v1{2, 7, 11, 15};
    vector<int> v = two_sum_solution(v1, 22);
    if (!v.empty()) {
        cout << "Indices:" << endl;
        for (auto i: v)
            cout << i << " ";
    }
    else (cout << "No matches found");
}

Leetcode统计：

运行时: 384毫秒，超过34.03%的C++在线提交两个求和。内存使用量:9.3MB，不到12.99%的C++在线提交的两个和。

Answer 1

只包含需要

的头文件。

在您的two_sum.h文件中，您不需要iostream，因为您没有使用它的任何功能。请记住，#include实际上是复制粘贴文件，所以如果您将这个头文件包含在多个文件中，它可能会减慢您的编译时间。

拆分声明和定义

通常，您会将文件分成两部分:头文件(通常以*.h, *.hpp, *.hh结尾)和源文件(通常以*.cpp, *.cc结尾)。头文件只包含声明，源文件包含实现。

因此，在您的示例中，头文件将如下所示：

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H

#include <vector>

std::vector<int> two_sum_solution(std::vector<int> &nums, int target);

#endif // LEETCODE_TWO_SUM_H

您的源文件将如下所示：

two_sum.cpp

#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
     ...
}

实际上，如果尝试将two_sum.h (与实现一起)包含到多个文件中，则会破坏一-定义规则。您的源文件将包含同一个函数的多个定义，链接器将显示一个错误。其中一种方法是标记函数inline，但您很可能想做前者。

头文件中没有using namespace

不要在头文件中执行using namespace或其任何变体。由于头文件是复制粘贴在多个源文件，它有可能造成恼人的错误。看这里

使用const参考

由于two_sum_solution没有修改nums向量，所以将其传递给const引用。

数组索引

size_t vs int数组索引

考虑使用大小_数组索引的t代替int

尽可能多地使用auto，

在您的代码中有几个实例可以使用auto而不是指定类型。示例：

auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);

最内循环是无意义的

。

简单地做

results.push_back(i);
results.push_back(j);

而且，一旦找到了解决方案，您可能需要立即返回结果。

Answer 2

您也许可以通过在给定数组的第一次迭代中创建一个值映射->索引来提高性能。

当前，您的程序执行以下操作(时间复杂性)：

1. 迭代数组的所有index, value对( O(n) )
2. 在数组中搜索target - value ( O(n) )
3. target - value查找索引( O(n) )

因为这些都是嵌套的，所以您可以找到O(n^2) (它不是n^3 ，因为每次迭代都没有完成最后的查找)。

我提出的解决办法：

1. 创建{value: index} ( O(n) )的地图/数据集
2. 迭代数组的index, value ( O(n) )
3. 从map/dict ( O(1) )查找和返回索引

def two_sum(numbers: list[int], target: int):
    lookup: dict = {
        value: index
        for index, value in enumerate(numbers)
    }
    for index, value in enumerate(numbers):
        match = target - value
        if search_index := lookup.get(match):
            return index, search_index
    return None

Answer 3

这对我来说很有趣，因为我来自C背景，在过去几年开始使用Python进行工作，所以我和您一样有相反的路径。当我开始使用Python时，我非常喜欢像您这样的解决方案，因为循环遍历列表非常明确。

然而，我后来了解到，当我使用标准库时，更熟练的Python程序员能够更好地理解我的代码。一旦我开始投资学习这些工具，它就会产生双重效果: 1)使我的代码更简洁；2)在时间和/或空间上更高效。

在本例中，我将解决来自combinations包的itertools问题：

from itertools import combinations

def two_sum(nums, target):
    pairs_with_indices = combinations(enumerate(nums), 2)

    # result is a generator comprehension.
    winning_pairs = ((index_i, index_j)
                     for (index_i, i), (index_j, j) in pairs_with_indices
                     if sum((i, j)) == target)

    # Insert as much error checking as you need...
    return next(winning_pairs)

使用Numpy可能有一个更简洁、更清晰的解决方案，它实际上是我的工作领域(数据科学)中的标准库，但并不是所有地方都是如此。

与您的代码不同的一点是:不存在任意一个错误的空间。根据我的经验，这样的代码

if match in (rest := nums[i + 1:]):
        match_at = rest.index(match)
        return i, match_at + i + 1

对我来说，写起来容易，读起来难，可维护性从简单到不可能。换句话说，用Python手动管理索引只会给我提供足够的绳子来使用，而标准库函数是一个很好的替代方法。