leetcode_1. 兩數(shù)之和
題目描述
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。示例:
給定 nums = [2, 7, 11, 15], target = 9因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
解題思路
利用哈希表，在迭代中判斷是否存在target-nums[i]這一元素，然后將tmp和其索引存入哈希表中
在python中可以用字典表示哈希表
代碼實(shí)現(xiàn)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ans_map = dict()
for i in range(0, len(nums)): # 一邊將列表中的數(shù)添加到字典中，一邊判斷兩數(shù)之差是否存在于字典中
temp = target - nums[i]
if temp in ans_map: # 判斷步驟
return [ans_map[temp], i]
ans_map[nums[i]] = i # 添加步驟（切記先判斷再添加，以免key沖突）
注意：此題不適合使用雙指針，因?yàn)樾枰葘?shù)組進(jìn)行排序，而排序后，數(shù)組的下標(biāo)會被打亂，結(jié)果要求返回的數(shù)字的下標(biāo)
leetcode_15. 三數(shù)之和
題目描述
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例：
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]來源：力扣（LeetCode）
鏈接：https://dev.lingkou.xyz/problems/3sum
解題思路
- 將數(shù)組排序
- 定義指針i,left,right。遍歷i,將問題轉(zhuǎn)化為在i之后的數(shù)組中尋找nums[i]+nums[left]+nums[right]=0的問題(即三數(shù)之和可以使用雙指針解決)
- 剪枝，去重
代碼實(shí)現(xiàn)
# 雙指針，所以先固定一個(gè)數(shù)字，用雙指針來找到另外兩個(gè)數(shù)字。注意記得剪枝
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
rnums=[] # 創(chuàng)建一個(gè)要返回的新列表
nums.sort() # 排序
n = len(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i-1]: # 避免重復(fù)項(xiàng)
continue
if nums[i] > 0:# 減少無關(guān)計(jì)算，定值大于 0 后，后面的都大于 0，沒必要進(jìn)行計(jì)算了
break
left = i + 1
right = n -1
while left < right:
cur_num = nums[i] + nums[left] + nums[right]
if cur_num == 0:
tmp = [nums[i], nums[left], nums[right]]
rnums.append(tmp)
while left < right and nums[left]==nums[left+1]: # 去重
left += 1
while left < right and nums[right]==nums[right-1]: # 去重
right -= 1
left += 1
right -= 1
elif cur_num > 0:
right -= 1
else:
left += 1
return rnums
leetcode_16. 最接近的三數(shù)之和
題目描述
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target。找出 nums 中的三個(gè)整數(shù)，使得它們的和與 target 最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。
例如，給定數(shù)組 nums = [-1，2，1，-4], 和 target = 1.
與 target 最接近的三個(gè)數(shù)的和為 2. (-1 + 2 + 1 = 2).
來源：力扣（LeetCode）
鏈接：https://dev.lingkou.xyz/problems/3sum-closest
解題思路
- 若數(shù)組長度小于3，返回[]
- 排序數(shù)組
- 遍歷數(shù)組
- 跳過重復(fù)元素
- 設(shè)置左指針left和右指針right，當(dāng)left < right 時(shí)，循環(huán)
- get_nums = nums[i] + nums[left] + nums[right]， 如果get_nums = target ,返回target
- 若abs(get_nums - target) < abs(res - target) 說明get_nums更靠近目標(biāo)，更新res
- 剪枝
- 返回結(jié)果
代碼實(shí)現(xiàn)
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums or len(nums) < 3: # 排除特殊情況
return None
nums.sort()
res = float("inf") # py用來表示正無窮
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: # 去重，提高效率
continue
left = i + 1
right = len(nums) - 1
while left < right:
get_nums = nums[i] + nums[left] + nums[right]
if get_nums == target:
return target
if abs(get_nums - target) < abs(res - target): # 說明get_nums更靠近目標(biāo)
res = get_nums # 更新內(nèi)容
if get_nums - target < 0:
left += 1
else:
right -= 1
return res
leetcode_18. 四數(shù)之和
題目描述
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums 和一個(gè)目標(biāo)值 target，判斷 nums 中是否存在四個(gè)元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重復(fù)的四元組。
注意：
答案中不可以包含重復(fù)的四元組。
示例：
給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/4sum
解題思路
- 排序
- 使用雙循環(huán)固定兩個(gè)數(shù)，用雙指針尋找另外兩個(gè)數(shù)，通過比較target大小,移動(dòng)指針
- 剪枝，去重
代碼實(shí)現(xiàn)
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
nums.sort()
n = len(nums)
for a in range(n - 3):
# 防止重復(fù)
if a > 0 and nums[a] == nums[a - 1]:
continue
# 當(dāng)最小值和都大于target， 跳出
if nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target:
break
# 數(shù)組最大值和小于target, 就遍歷下一個(gè)
if nums[a] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
continue
for b in range(a + 1, n - 2):
# 防止重復(fù)
if b - a > 1 and nums[b] == nums[b - 1]:
continue
if nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target:
break
if nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target:
continue
# 雙指針
left = b + 1
right = n - 1
while left < right:
tmp = nums[a] + nums[b] + nums[left] + nums[right]
if tmp == target:
res.append([nums[a], nums[b], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif tmp > target:
right -= 1
else:
left += 1
return res
