LeetCode 双刀流： 1. Two Sum

1. Two Sum

我们挑选 LeetCode 中的 1. Two Sum 作为我们实作练习的第一题，这个题目也是很多人进入 LeetCode 题目中的第一个题目。

比起一题解完就换下一题这样的方式，我们更建议花多一点在一个题目中，尽可能地持续迭代、持续优化并且思考沈淀，让你从一个题目掌握到更深更广的效益。因此我们建议在进入「一个题目」的解题过程时，可以将解题过程分成四个阶段，这里我们就先从「#动手之前先思考」这个步骤开始：

先看一下题目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

再搭配范例理解题目

• Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

• Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

这个题目很直观，从 nums 中找出两数相加等於 target 的两数索引值，回传两数索引值组成的容器（List 或 Object）。从题目给的限制及叙述中，可以得知必然只会有一组要求符合的结果，没有规定回传资料的顺序。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：双层回圈

这个题目回到要求来看：

从 nums 中找出两数相加等於 target 的两数索引值

需要同时找到两件元素：(1) 两数 (2) 索引值 ，并且去定义出相等的条件，初步的逻辑如下：

if num1 + num2 == target:
    return [i, j]

再来就是该怎麽去找出 num1 、 num2 和 i、j 索引值呢？这里我们第一种方法想到的是用索引值进行两个回圈的迭代：

for i in ragne(len(nums)):
    for j in ragne(len(nums)):
        num1 = nums[i]
        num2 = nums[j]

这样一来就可以得到 nums 所有的任两数组合，分别指定到 num1 和 num2 变数中。只是这个写法有一个小疑虑，这个写法会把 nums 中的 任两数的排列组合 都找出来，这里的任两数会包含重复出现（也就是自己跟自己也是一种组合）。不过，根据题目要求「任两数」是「任意两个不重复的数」进行相加，因此可以改写成：

for i in ragne(len(nums)):
    for j in ragne(i+1, len(nums)):
        num1 = nums[i]
        num2 = nums[j]

第二个回圈只需要针对第一个回圈还没有计算过的位置继续往後即可。

那我们先用 Python 实作看看

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

也可以用 JavaScript 复刻一次

var twoSum = function(nums, target) {
    for(var i = 0 ; i < nums.length ; i++){
        for(var j = i ; j < nums.length ; j++ ){
            if(  nums[i] + nums[j]  == target ){
                return [i, j];
            }
        }
    }
};

方法 ②：一层回圈 + 杂凑表（Hash Table）

第一种方法我们利用两个回圈把任两数的排列组合全部找出来，第二个想法是能否 只使用一个回圈 就解决这个问题呢？若只使用一个回圈的话，那是必须要把某些资讯暂存起来。原本题目要求的是：

num1 + num2 == target

我们可以题目的要求转个方向：

target - num1 = num2

如此一来，在一个回圈中我们可以将 num1 暂存起来，并且去检查已经存过的 num1 是否等於现在所需要的 num2。需要一个可以自定义 key-value 的资料结构来暂存 num1，这里可以使用 Python 中的 dictionary 或是 JavaScript 中的 Object ，这种类似杂凑表（Hash Table）的资料结构。这个想法可以写成这样：

d = {}
num2 = target - num1
if num2 in d:
    return [i, j]

但因为需要 num1、num2 的索引值，所以需要暂存的资讯中，也要把索引值记录下来：

d = {}
num1 = nums[i]
num2 = target - num1
if num2 in d:
    return [d[num2], i]
d[num2] = i

那我们先用 Python 实作看看

class Solution(object):
    def twoSum(self, nums, target):
        d = {}
        for i in range(len(nums)):
            num1 = nums[i]
            num2 = target - num1
            if num2 in d:
                return [d[num2], i]
            d[num1] = i

也可以用 JavaScript 复刻一次

var twoSum = function(nums, target) {
    var d = {};
    for(var i = 0 ; i < nums.length ; i++){
        var num1 = nums[i];
        var num2 = target - num1;
        if(d[num2] >= 0){
            return [d[num2], i]
        d[num1] = i;
    }
};

方法 ③：半个回圈 + 双指针（Two Pointer）

第三种方法我们使用双指针（Two Pointer）的方法来实现，双指针简单来说就是自定义位置指向元素，移动指标位置来调整想要从容器中取出的数值：

i = 0
j = len(nums) - 1
while ...:
    if ...:
        i = i + 1
    else:
        j = j - 1

根据题目要求，这里可以利用两个指针计算两个元素和，不符合则往中间移动直到满足题目要求：

while (nums[i] + nums[j] != target):
    if (nums[i] + nums[j] > target):
        j = j - 1
    else:
        i = i + 1

那我们先用 Python 实作看看

class Solution(object):
    def twoSum(self, nums, target):
        i = 0
        j = len(nums) - 1
        
        while (nums[i] + nums[j] != target):
            if (nums[i] + nums[j] > target):
                j = j - 1
            else:
                i = i + 1
                
        return [i, j]

也可以用 JavaScript 复刻一次

var twoSum = function(nums, target) {
    
    var i = 0;
    var j = nums.length - 1;
    while (nums[i] + nums[j] != target){
        if (nums[i] + nums[j] > target)
            j = j - 1
        else
            i = i + 1
    }

    return [i, j]
};

但是这个方法跑测试案例的时候会过，但实际上在执行的时候是不会过的。原因是这里双指针的移动必须是原始资料已排序的情况下才能这样动，所以其实更适合的是 167. Two Sum II - Input array is sorted 情境。若想将该题调整的话，记得也要将原始的索引值也要记录下来才可以，过程上会比较麻烦，可以参考以下做法：

nums1 = nums[i]
nums2 = nums[j]

i = raw_nums.index(nums1)
if nums1 == nums2:
    j = raw_nums[i+1:].index(nums2)
    return [i, i+1+j]
j = raw_nums.index(nums2)
return [i, j]

反思沉淀

进入「一个题目」的解题过程时，可以分成「#动手之前先思考 → #初探直觉解 → #刻意优化 → #举一反三」几个阶段的优化过程。这个题目有两件事情是值得注意的：

1. 方法一到方法三的持续优化
2. Python 和 JavaScript 语法转换

「如何最大化一个题目的效益」也是刷题过程中重要的关键，如何从一个尽可能地持续迭代、持续优化并且思考沈淀，让你从一个题目掌握到更深更广的效益。虽然只有一个题目，不过我们就学习到两种语言共计六种写法，这就是所谓的最大化一个题目中可以掌握的方法与技巧。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 15. 3Sum
• 18. 4Sum
• 167. Two Sum II - Input array is sorted
• 170. Two Sum III - Data structure design
• 653. Two Sum IV - Input is a BST

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。