代码随想录day6 | 1. 两数之和 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

**代码随想录 Day6**

## 一、两数之和### 题目描述给定一个整数数组 `nums` 和一个目标值 `target`，找出两个数字的下标，使得它们加起来等于 `target`。你可以假设每个输入只有一种解。

### 示例1:

* 输入：`nums = [2,7,11,15]`, `target =9`
* 输出:`[0,1]`

### 示例2:

* 输入：`nums = [3,2,4], target =6`
* 输出:`[1,2]`

### 解决方案我们可以使用哈希表来解决这个问题。首先，我们遍历数组 `nums`，将每个数字及其下标存储在哈希表中。如果我们找到了一个数字 `x`，使得 `target - x` 也存在于哈希表中，那么我们就找到了一对数字，它们加起来等于 `target`。

def twoSum(nums, target):
 num_dict = {}
 for i, num in enumerate(nums):
 if target - num in num_dict:
 return [num_dict[target - num], i]
 num_dict[num] = i return []

## 二、四数相加II### 题目描述给定一个整数数组 `nums` 和一个目标值 `target`，找出四个数字的下标，使得它们加起来等于 `target`。你可以假设每个输入只有一种解。

### 示例1:

* 输入：`nums = [1,0,-1,0,-2,2], target =0`
* 输出:`[3,5]`

### 解决方案我们可以使用哈希表来解决这个问题。首先，我们遍历数组 `nums`，将每个数字及其下标存储在哈希表中。如果我们找到了三个数字 `x`, `y`, 和 `z`，使得 `target - x - y - z` 也存在于哈希表中，那么我们就找到了一组四个数字，它们加起来等于 `target`。

def fourSum(nums, target):
 num_dict = {}
 for i, num in enumerate(nums):
 if num not in num_dict:
 num_dict[num] = [i]
 else:
 num_dict[num].append(i)
 result = []
 nums.sort()
 for i in range(len(nums)):
 for j in range(i +1, len(nums)):
 left, right = j +1, len(nums) -1 while left < right:
 current_sum = nums[i] + nums[j] + nums[left] + nums[right]
 if current_sum == target:
 result.append([nums[i], nums[j], nums[left], nums[right]])
 # Skip duplicates 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 current_sum < target:
 left +=1 else:
 right -=1 return result

## 三、赎金信### 题目描述给定两个字符串 `s1` 和 `s2`，找出其中一个字符串的子串，使得它在另一个字符串中出现。

### 示例1:

* 输入：`s1 = "hello"`, `s2 = "world"`
* 输出:`[]`

### 解决方案我们可以使用哈希表来解决这个问题。首先，我们遍历第一个字符串 `s1`，将每个子串及其出现次数存储在哈希表中。如果我们找到了一个子串 `x`，使得它也存在于第二个字符串 `s2` 中，那么我们就找到了一对子串，它们相似。

def findSubstring(s1, s2):
 num_dict = {}
 for i in range(len(s1)):
 for j in range(i +1, len(s1) +1):
 substring = s1[i:j]
 if substring not in num_dict:
 num_dict[substring] =1 else:
 num_dict[substring] +=1 result = []
 for i in range(len(s2)):
 for j in range(i +1, len(s2) +1):
 substring = s2[i:j]
 if substring in num_dict and num_dict[substring] >0:
 result.append([s1, s2])
 # Skip duplicates while i < len(s2) and s2[i] == s2[i +1]:
 i +=1 while j < len(s2) and s2[j -1] == s2[j]:
 j -=1 i +=1 j -=1 return result

## 四、三数之和### 题目描述给定一个整数数组 `nums` 和一个目标值 `target`，找出三个数字的下标，使得它们加起来等于 `target`。你可以假设每个输入只有一种解。

### 示例1:

* 输入：`nums = [-1,0,1,2,-1,-4]`, `target =0`
* 输出:`[(-1,-1,2), (-1,0,1)]`

### 解决方案我们可以使用哈希表来解决这个问题。首先，我们遍历数组 `nums`，将每个数字及其下标存储在哈希表中。如果我们找到了两个数字 `x` 和 `y`，使得 `target - x - y` 也存在于哈希表中，那么我们就找到了一组三个数字，它们加起来等于 `target`。

def threeSum(nums):
 num_dict = {}
 for i, num in enumerate(nums):
 if num not in num_dict:
 num_dict[num] = [i]
 else:
 num_dict[num].append(i)
 result = []
 nums.sort()
 for i in range(len(nums)):
 for j in range(i +1, len(nums)):
 left, right = j +1, len(nums) -1 while left < right:
 current_sum = nums[i] + nums[j] + nums[left]
 if current_sum ==0:
 result.append([nums[i], nums[j], nums[left]])
 # Skip duplicates 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 current_sum < 0:
 left +=1 else:
 right -=1 return result

## 五、四数之和### 题目描述给定一个整数数组 `nums` 和一个目标值 `target`，找出四个数字的下标，使得它们加起来等于 `target`。你可以假设每个输入只有一种解。

### 示例1:

* 输入：`nums = [1,0,-1,0,-2,2], target =0`
* 输出:`[(-2,-1,1,2), (-2,0,0,2)]`

### 解决方案我们可以使用哈希表来解决这个问题。首先，我们遍历数组 `nums`，将每个数字及其下标存储在哈希表中。如果我们找到了三个数字 `x`, `y`, 和 `z`，使得 `target - x - y - z` 也存在于哈希表中，那么我们就找到了一组四个数字，它们加起来等于 `target`。

def fourSum(nums, target):
 num_dict = {}
 for i, num in enumerate(nums):
 if num not in num_dict:
 num_dict[num] = [i]
 else:
 num_dict[num].append(i)
 result = []
 nums.sort()
 for i in range(len(nums)):
 for j in range(i +1, len(nums)):
 left, right = j +1, len(nums) -1 while left < right:
 current_sum = nums[i] + nums[j] + nums[left] + nums[right]
 if current_sum == target:
 result.append([nums[i], nums[j], nums[left], nums[right]])
 # Skip duplicates 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 current_sum < target:
 left +=1 else:
 right -=1 return result

以上是解决三