LeetCode之3Sum

题目内容

输入一个数组，例如{-1 0 1 2 -1 -4}，从数组中找三个数（a,b,c），使得其和0，输出所有的（a,b,c）组合。

要求abc不能重复，并且a<=b<=c。

例：

S = {-1, 0, 1, 2, -1, -4}；

输出：

(-1, 0 ,1)

(-1, -1, 2)

分析

一看到题目，不问代码行数，不问时间复杂度，便排出三个循环。。但是循环非常耗时，显然不是题目的本意。想了好长时间没有什么进展。

先将给定数组排序，然后指定一个数，在数组中找出两个数并且这两个数的和是目标数值的相反数：【LeetCode】3Sum 解题报告

在网上找到了篇比较有新意的文章：[3Sum algorithm - 非常容易理解的实现 （java)] 。

---

最后发现维基百科中就有收录：维基百科—3SUM ，还有更一般的情形 N SUM。

 sort(S);
 for i=0 to n-3 do
    a = S[i];
    start = i+1;
    end = n-1;
    while (start < end) do
       b = S[start]
       c = S[end];
       if (a+b+c == 0) then
          output a, b, c;
          // Continue search for all triplet combinations summing to zero.
           end = end - 1
       else if (a+b+c > 0) then
          end = end - 1;
       else
          start = start + 1;
       end
    end
 end

伪代码还挺容易理解的。

Other

因为知乎上有人宣称证明了哥德巴赫猜想的原因，这两天还特意了解了下猜想证明的历史，“1+2”、“1+3”之类的证明，虽然一点也没看懂。感觉数学真的很有魅力，严谨清晰的逻辑，精妙完美的结论，自然界中的一切每时每刻都在遵循着其中的规律运行，更加感慨于人类的智慧，都找不到合适的赞美的词了。

“超越数”、“黄金分割”、“哥德巴赫猜想”、“黎曼猜想”…

停下思绪，回到现实：当你理解它的时候你觉得进入了天堂，当你不理解它的时候你仿佛进入了地狱，看哭了…