查找 2

Posted on | | Visitors: ℃
Words count in article: 1.3k

查找2

1. 两数之和

简单题

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力法O（N^2）

1
2
3
4
5
def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i+1 , len(nums), 1):
            if nums[j] == target - nums[i]:
                return [i , j]

使用哈希表

1
2
3
4
5
6
7
def twoSum(self, nums: List[int], target: int) -> List[int]:
	hash_tab = {}
       for i in range(len(nums)):
           if target - nums[i] in hash_tab.keys():
               return [i, hash_tab[target - nums[i]]]
           else:
               hash_tab[nums[i]] = i

如果返回的不是键值，而是对应的结果，可以用

排序+双指针

首先可以先排序，此时的数组是从小到大的，使用两个指针，分别从前后两个方向上去找

单步：

  1. 前指针的数值求补数，直到后指针找到
  2. 找到以后，前指针向后，后指针向前
  3. 如果发现数值已经大于该数字，结束后指针查找，重新开始前指针后移

15. 三数之和

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

此题虽然合上述的问题相似，但是没有利用哈希表来做了，因为哈希表利用了哈希的程序便利性，使用排序加双指针会更好

  1. 首先求的和是0，当从小到大排序完成后，第一个数字必须是小于0的，如果大于0说明已经结束了
  2. 此时双指针一个从上一个循环的值开始（pre），一个从数组尾端开始（end）
  3. 两个while 同时逼近，target = -nums[i] - nums[pre]首先先动后面的，如果小于taget，跳出，前指针后移，如果大于，后指针前移查找直到相等，或者前后指针相同
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
def threeSum(self, nums: List[int]) -> List[List[int]]:
    res = []
    nums.sort()
    target = 0
    for i in range(len(nums)):
        if nums[i] > 0: break
        if i != 0 and nums[i] == nums[i-1]:
            continue
        pre = i + 1
        end = len(nums) - 1

        while pre < end:
            sum = nums[end] + nums[pre]
            if -nums[i] > sum:
                pre += 1
            elif -nums[i] < sum:
                end -= 1
            elif -nums[i] == sum:
                res.append([nums[i], nums[pre], nums[end]])
                pre += 1
                end -= 1
                while pre < end and nums[pre] == nums[pre - 1]:
                    pre += 1
                while pre < end and nums[end] == nums[end + 1]:
                    end -= 1
    return res

16. 最接近的三数之和

1
2
3
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案

  1. 先排序，第一个是最小的i，
  2. 然后往后查找，如果三个数字和等于target就返回，如果大于，说明可以end调小一点， 如果小于说明可以pre调大一点
  3. 每一次运算完检测差的绝对值是否变小了，如果变小了就记录当前的总和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSumClosest(self, nums: List[int], target: int) -> int:
    nums.sort()
    temp = nums[0] + nums[1] + nums[2]
    res = abs(nums[0] + nums[1] + nums[2] - target)
    for i in range(len(nums) - 2):
        if i != 0 and nums[i] == nums[i - 1]:
            continue
        pre = i + 1
        end = len(nums) - 1
        while pre < end:
            t_sum = nums[pre] + nums[i] + nums[end]
            if t_sum == target:
                return target
            else:
                if abs(target - t_sum) < res:
                    res = abs(target - t_sum)
                    temp = t_sum
            if t_sum < target:
                pre += 1
            else:
                end -= 1

    return temp

92 ms, 在所有 Python3 提交中击败了94.96%的用户

18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

和三数字之和很类似，应该是在之前的上面增加一个循环

由于输出的是数字组合，用排序和双指针实现，首先是排序，确定第一个最小的值，然后确定第二小的值，剩下两个双指针走

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
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
    res = []
    nums.sort()
    for i in range(len(nums) - 3):
        if i != 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, len(nums)-2, 1):

            if j > i+1 and nums[j] == nums[j-1]:
                continue
            pre = j + 1
            end = len(nums) - 1

            while pre < end:
                sum = nums[end] + nums[pre] +  nums[i] + nums[j]
                if target > sum:
                    pre += 1
                elif target < sum:
                    end -= 1
                elif target == sum:
                    res.append([nums[i], nums[j], nums[pre], nums[end]])
                    pre += 1
                    end -= 1
                    while pre < end and nums[pre] == nums[pre - 1]:
                        pre += 1
                    while pre < end and nums[end] == nums[end + 1]:
                        end -= 1
    return res

由于是N^3的复杂度，速度还是很慢的，可以提前考虑一些极端情况优化下

-------------本文结束感谢您的阅读 :D -------------
Show comments from Gitment