Scott's Blog

学则不固, 知则不惑

0%

算法题: 两数之和与三数之和

发表于 更新于 分类于 阅读次数： Valine：

📌 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

两数之和

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

1
2
3
4
5
6
7
def twoSum():
    hashtable = dict()
    for i, num in enumerate(nums):
        if target - num in hashtable:
            return [hashtable[target - num], i]
        hashtable[nums[i]] = i
    return []

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

算法流程：

  1. 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
  2. 对数组进行排序。
  3. 遍历排序后数组
1
2
3
4
5
6
- 若 nums[i] > 0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
- 对于重复元素：跳过，避免出现重复解
- 令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
    - 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
    - 若和大于 0，说明 nums[R] 太大，R 左移
    - 若和小于 0，说明 nums[L] 太小，L 右移

简单演示：

1
2
3
4
[-1, 0, 1, 2, -1, -4]
[ I, L, 1, 2, -1,  R]
[ I, 0, L, 2, -1,  R]
[ I, 0, L, 2,  R, -4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
nums = [-1, 0, 1, 2, -1, -4]
# 输出：[[-1,-1,2],[-1,0,1]]


def threeSum(nums):
    n = len(nums)
    res = []
    # null, 长度 < 3, 返回 []
    if(not nums or n < 3):
        return []
    # 排序方便操作
    nums.sort()
    res = []
    for i in range(n):

        # 已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果
        if(nums[i] > 0):
            return res
        # 连续两个重复值，前面已经尝试过所有组合，所以跳过    
        if(i > 0 and nums[i] == nums[i-1]):
            continue

        # L 从 i+1 开始，R 从数组长度 -1 开始
        L = i+1
        R = n-1
        while(L < R):
            if(nums[i]+nums[L]+nums[R] == 0):
                res.append([nums[i], nums[L], nums[R]])
                while(L < R and nums[L] == nums[L+1]):
                    L = L+1
                while(L < R and nums[R] == nums[R-1]):
                    R = R-1
                L = L+1
                R = R-1
            elif(nums[i]+nums[L]+nums[R] > 0):
                R = R-1
            else:
                L = L+1
    return res

threeSum(nums)