算功@LeetCode:TwoSum

作者: 苏尚君 | 来源:发表于2017-04-06 01:02 被阅读62次

Log

【170405】恢复算法题训练首日，已经比较晚了，先完成了 Python 第一版代码。至于代码优化（例如缩短运行时）、其他语言下的写法（C？CPP？Java？…）则暂时搁置。具体如何制订个规则来保证自己会回头去重新研究，再议。最迟在 170409 结束前应给出一个初版。
【170406】重新改了一下报告的格式，以提交次数为三级标题，把「语言」放到报告中作为一个项目；然后把提交 01 的 Python 代码该成了 C++ 的写法（提交 02）
【170407】补充了一种优化思路对应的代码和结果。补充了参考答案对应的思路和结果。

题目

Two Sum

【题目类型备注】

O(n^2)优化, O(n), 哈希表, HashMap

提交

01

【语言】

Python

【时间】

170405

【思路】

〖复杂度？〗由于有且仅有 1 个答案，所以不可避免地要遍历数组中的所有二元数对，因此复杂度应该是 $O(n^2)$ 的
〖能否剪枝？〗能。
对于任意给定的二元数对 (a, b) 来说，和是唯一的。因此如果要写 2 个 for 循环嵌套，内层循环不需要再次遍历外层循环此前已经遍历过的数对。

> 例如对于 [1, 2, 3, 4, 5]，若 i = 1 时 j = 3 已经遍历过了 (1, 3)，那么当 i = 3 时就不必再遍历一次 j = 1

由于不会用到自身，所以每次遍历时，内层循环只要从 (i + 1) 开始即可
不过如果仅仅是这样剪枝，遍历次数的复杂度也仍然是 $O(n^2)$
〖什么时候停？〗因为有且仅有 1 个答案，在内层循环中找到即可停止

【代码】

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lengthOfArray = len(nums)
        answer = []
        for i in range(lengthOfArray - 1):
            for j in range(i + 1, lengthOfArray):
                if (nums[i] + nums[j] == target):
                    answer = [i, j]
                    return answer

【结果】

运行时：492 ms

报告链接：https://leetcode.com/submissions/detail/99180059/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 45.85% of python submissions.

（虽然超过了 45% 的选手，不过看了下其他语言，蛇语就是慢啊……）

02

【语言】

C++

【时间】

170406

【思路】

同提交 01

【代码】

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> indices = {};
        int lenOfNums = nums.size();
        for (int i=0; i < lenOfNums - 1; i++)
        {
            for (int j=i+1; j < lenOfNums; j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    indices.push_back(i);
                    indices.push_back(j);
                    return indices;
                }
            }
        }
    }
};

【结果】

运行时：146 ms

报告链接：https://leetcode.com/submissions/detail/99279559/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 26.43% of cpp submissions.

（虽然时间变成了大约是原来的 1/3，但看了一下我的水平，似乎在 CPP 提交者中成了渣渣…看来这题应该有更优化的算法，需要再思考下）

03

【语言】

C++

【时间】

1704006

【思路】

之前的 2 次提交（01，02）的复杂度都是 $O(n^2)$ 的。之前听说过一句话：

有经验的程序员看到复杂度是 $O(n^2)$ 时，本能地会试图去把程序优化成 $O(n logn)$

那么如何优化成 n logn 呢？考虑到快速排序的思想，因此我考虑了分治策略：把大问题的解，分解成若干小问题的解

如何分解为小问题的解？大问题要求的解是：

一对下标 [i, j]，满足：nums[i] + nums[j] == target

能够分解成若干组下标吗？沿着这个思路我想不通。但能不能分解成 2 个下标呢？就像快排一样：

我能不能以某个数为中轴（pivot）、假设中轴就是要找的数之一，向左去找看看是否有配对的数，向右去找找是否有配对的数，找到了就返回该数对应的下标

这样就分解成了 2 个小问题：从找 2 个数的大问题，变成了各找 1 个数的小问题

然后每次找这个数时，我可以每次都去找中轴，如果找到了就返回该数的坐标，否则左边找、右边找

再辅以一些特殊情况的处理（例如：本例中实现分治，需要递归，那么递归的终止条件就是那些特殊情况；以及，找到了数以后如何表示……）

于是就有了下面的这两段差不太多的代码

【代码】

class Solution {

public:

    int helper(vector<int>& arr, int target, int begin, int end) {
        //if only 1 element
        if (end - begin == 0)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else
          {
            return -1;
          }
        }
        //if 2 elements
        if (end - begin == 1)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else if (target == arr[end])
          {
            return end;
          }
          else
          {
            return -1;
          }
        }
        //if 3+ elements
        if (end - begin >= 2)
        {
          int mid = begin + (end - begin)/2;
          int x = helper(arr, target, begin, mid-1);
          int y = helper(arr, target, mid+1, end);
          if (-1 != x)
          {
            return x;
          }
          else if (-1 != y)
          {
            return y;
          }
          else
          {
            return -1;
          }
        }
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        int lenOfNums = nums.size();
        int x, y;

        //if (2 == lenOfNums)
        //{
        //  vector<int> indices = {0, 1};
        //  return indices;
        //}
        for (int i=1; i<lenOfNums; i++)
        {
          if (nums[0] + nums[i] == target)
          {
            vector<int> indices = {0, i};
            return indices;
          }
        }

        for (int i=1; i<lenOfNums-1; i++)
        {
          x = helper(nums, target-nums[i], 0, i-1);
          y = helper(nums, target-nums[i], i+1, lenOfNums-1);
          if (-1 != x)
          {
            vector<int> indices = {x, i};
            return indices;
          }
          else if (-1 != y)
          {
            vector<int> indices = {i, y};
            return indices;
          }
          else
          {
            continue;
          }
        }
       
    }
};

class Solution {

public:

    int helper(vector<int>& arr, int target, int begin, int end) {
        //if only 1 element
        if (end - begin == 0)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else
          {
            return -1;
          }
        }
        //if 2 elements
        if (end - begin == 1)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else if (target == arr[end])
          {
            return end;
          }
          else
          {
            return -1;
          }
        }
        //if 3+ elements
        if (end - begin >= 2)
        {
          int mid = begin + (end - begin)/2;
          if (target == arr[mid])
          {
              return mid;
          }
          int x = helper(arr, target, begin, mid-1);
          int y = helper(arr, target, mid+1, end);
          if (-1 != x)
          {
            return x;
          }
          else if (-1 != y)
          {
            return y;
          }
          else
          {
            return -1;
          }
        }
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        int lenOfNums = nums.size();
        int x, y;

        //if (2 == lenOfNums)
        //{
        //  vector<int> indices = {0, 1};
        //  return indices;
        //}
        for (int i=1; i<lenOfNums; i++)
        {
          if (nums[0] + nums[i] == target)
          {
            vector<int> indices = {0, i};
            return indices;
          }
        }

        for (int i=1; i<lenOfNums-1; i++)
        {
          x = helper(nums, target-nums[i], 0, i-1);
          y = helper(nums, target-nums[i], i+1, lenOfNums-1);
          if (-1 != x)
          {
            vector<int> indices = {x, i};
            return indices;
          }
          else if (-1 != y)
          {
            vector<int> indices = {i, y};
            return indices;
          }
          else
          {
            continue;
          }
        }
       
    }
};

【结果】

一个用了 382 ms，一个用了 492 ms

越改越慢。。。

04

【语言】

C++

【时间】

170407

【思路】

考虑提交 03 中，似乎在分治时没有在找到答案后就返回，而是在「左分治」完成后就算找到了答案（没有返回 -1）也把「右分治」跑一遍——然而这显然是不必要的：由于有且仅有 1 个答案，而且在进入分治策略时，已经假定了外层循环 i 对应的下标对应的数字是要找的其中一个，那么只要任一分治找到了答案，就没必要继续找另一边了。

于是我考虑优先考虑「左分治」：如果左边先找到了，就返回，不需要再计算「右分治」的结果。

【代码】

class Solution {

public:

    int helper(vector<int>& arr, int target, int begin, int end) {
        //if only 1 element
        if (end - begin == 0)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else
          {
            return -1;
          }
        }
        //if 2 elements
        if (end - begin == 1)
        {
          if (target == arr[begin])
          {
            return begin;
          }
          else if (target == arr[end])
          {
            return end;
          }
          else
          {
            return -1;
          }
        }
        //if 3+ elements
        if (end - begin >= 2)
        {
          int mid = begin + (end - begin)/2;
          int x = helper(arr, target, begin, mid-1);
          if (-1 != x)
          {
            return x;
          }
          else 
          {
              int y = helper(arr, target, mid+1, end);
              if (-1 != y)
              {
                  return y;
              }
              else
              {
                return -1;
              }
            }
        }
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        int lenOfNums = nums.size();
        int x, y;

        //if (2 == lenOfNums)
        //{
        //  vector<int> indices = {0, 1};
        //  return indices;
        //}
        for (int i=1; i<lenOfNums; i++)
        {
          if (nums[0] + nums[i] == target)
          {
            vector<int> indices = {0, i};
            return indices;
          }
        }

        for (int i=1; i<lenOfNums-1; i++)
        {
          x = helper(nums, target-nums[i], 0, i-1);
          if (-1 != x)
          {
            vector<int> indices = {x, i};
            return indices;
          }
          else
          {
              y = helper(nums, target-nums[i], i+1, lenOfNums-1);
              if (-1 != y)
              {
                vector<int> indices = {i, y};
                return indices;
              }
          }
        }
       
    }
};

【结果】

这次用了 265 ms，比昨天那个提交好点。但还是很头疼……我的算法设计出了什么大问题么，为什么我以为的更低的复杂度导致了更多的计算时间？

00

参考解法：

注意：其中的 C++ 和 Java 解法有个小瑕疵，导致答案和题意不符，不过仔细看一下就明白。瑕不掩瑜

参考答案的复杂度居然直接降到了 $O(n)$ ！惊喜超过了懊恼，太棒了。所有解法都巧妙运用了 HashMap 这类的数据结构，太棒了！

自己实现一遍最优解：

。。。

算功@LeetCode:TwoSum

Log

题目

提交

01

02

03

04

00

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读