发展算法思维
我遇到了一个问题，在给定的整数数组中，我需要找到满足给定和的对。
我想到的第一个解决方案是检查所有可能的对，这大约需要O(n^2)时间，但面试官要求我提出改进的运行时间，我建议对数组进行排序，然后进行二进制搜索，但这也是O(nlogn)。
总体而言，我没有想出O(n)解决方案。我在谷歌上发现，这可以通过使用set的额外内存来实现。
我知道思考算法不可能有任何固定的规则，但我很乐观，认为在数组上思考算法时，一定会有一些启发式或心理模型。我想知道是否有任何通用的策略或特定于数组的想法，可以帮助我更多地探索解决方案，而不是表现得死气沉沉。
回答 1
Stack Overflow用户
发布于 2016-10-10 18:41:15
一般来说，先考虑如何天真地做这件事。如果在面试中，明确你在做什么，说“嗯，朴素的算法将是……”。
然后看看您是否可以看到任何重复的工作或多余的步骤。面试问题往往有点不现实，是数学特例类型的问题。真正的问题更多地归结为使用哈希表或排序数组。排序是N log N，但它使所有后续搜索都是O log N，因此通常是值得对数据进行排序的。如果数据是动态的，则通过二进制搜索树(C++ "set")对其进行排序。
其次，你可以“分而治之”还是“建立”。N=2的情况微不足道吗？在这种情况下，我们能否将N=4分成两个N=2的情况，以及另一个积分步骤？您可能需要将输入分为两组，低和高，在这种情况下，它是“分而治之”，或者您可能需要从随机对开始，然后合并到4，8，等等，在这种情况下，它是“构建”。
如果问题是几何问题，你能利用局部连贯性吗？如果问题是现实的而不是数学的，并且有典型的输入可以利用(真正的旅行推销员不会在随机网格上的城市之间旅行，而是通过一个枢纽和辐射状的运输系统，快速道路连接主要城市和慢速道路，然后分支到客户目的地)？
https://stackoverflow.com/questions/39954760
复制相似问题
腾讯云开发者
