雷神代刷推广网站,全国最好装修公司排行榜,衡阳做网站公司,网络设计属于什么专业文章目录 第一题: 两数之和题目描述示例 解题思路Go语言实现 - 一遍哈希表法C实现算法分析 排序和双指针法Go语言实现 - 排序和双指针法C算法分析 暴力法Go语言实现 - 暴力法C算法分析 二分搜索法Go语言实现 - 二分搜索法C算法分析 第一题: 两数之和
题目描述
给定一个整… 文章目录 第一题: 两数之和题目描述示例 解题思路Go语言实现 - 一遍哈希表法C实现算法分析 排序和双指针法Go语言实现 - 排序和双指针法C算法分析 暴力法Go语言实现 - 暴力法C算法分析 二分搜索法Go语言实现 - 二分搜索法C算法分析 第一题: 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那两个整数并返回他们的数组索引。 你可以假设每种输入只会对应一个答案。但是你不能重复利用这个数组中同样的元素。
示例
给定 nums [2, 7, 11, 15], target 9
因为 nums[0] nums[1] 2 7 9
所以返回 [0, 1]解题思路
暴力法双重循环遍历数组中的每个数寻找是否存在一个数与它相加等于目标值。两遍哈希表法遍历数组将每个数及其索引存入哈希表然后再次遍历数组查找 target - nums[i] 是否在哈希表中。一遍哈希表法遍历数组对于每个数查找 target - nums[i] 是否在哈希表中如果在直接返回结果如果不在将当前数存入哈希表。
截图为Go语言的测试
Go语言实现 - 一遍哈希表法
package main
func twoSum(nums []int, target int) []int {hashTable : make(map[int]int)for i, num : range nums {complement : target - numif index, ok : hashTable[complement]; ok {return []int{index, i}}hashTable[num] i}return nil
}C实现
#include vector
#include unordered_mapclass Solution {
public:std::vectorint twoSum(std::vectorint nums, int target) {std::unordered_mapint, int hashTable;for (int i 0; i nums.size(); i) {int complement target - nums[i];if (hashTable.find(complement) ! hashTable.end()) {return {hashTable[complement], i};}hashTable[nums[i]] i;}return {};}
};算法分析
时间复杂度O(n)其中 n 是数组中的元素数量。我们只遍历了包含有 n 个元素的列表两次。在哈希表中的操作时间复杂度为 O(1)。空间复杂度O(n)所需的额外空间取决于哈希表中存储的元素数量该表中存储了 n 个元素。 这个Go语言实现的代码简单易懂效率较高适合解决这类问题。
排序和双指针法 首先创建一个数组包含原始数组的元素和它们的索引。 然后根据数组元素对数组进行排序。 使用两个指针一个从开始最小元素的位置另一个从结束最大元素的位置。 比较两个指针指向的元素之和与目标和 如果和等于目标和返回两个元素的索引。如果和小于目标和移动左侧指针使它指向一个更大的数。如果和大于目标和移动右侧指针使它指向一个更小的数。 这种方法的关键在于排序后我们可以使用双指针高效地找到两个数使得它们的和等于目标和。
Go语言实现 - 排序和双指针法
package main
import (sort
)
type Pair struct {Value intIndex int
}
func twoSum(nums []int, target int) []int {pairs : make([]Pair, len(nums))for i, num : range nums {pairs[i] Pair{Value: num, Index: i}}sort.Slice(pairs, func(i, j int) bool {return pairs[i].Value pairs[j].Value})left, right : 0, len(nums)-1for left right {sum : pairs[left].Value pairs[right].Valueif sum target {return []int{pairs[left].Index, pairs[right].Index}} else if sum target {left} else {right--}}return nil
}C
#include vector
#include algorithm
#include utilityclass Solution {
public:std::vectorint twoSum(std::vectorint nums, int target) {std::vectorstd::pairint, int numWithIndex;for (int i 0; i nums.size(); i) {numWithIndex.push_back({nums[i], i});}std::sort(numWithIndex.begin(), numWithIndex.end());int left 0, right nums.size() - 1;while (left right) {int sum numWithIndex[left].first numWithIndex[right].first;if (sum target) {return {numWithIndex[left].second, numWithIndex[right].second};} else if (sum target) {left;} else {--right;}}return {};}
};
算法分析
时间复杂度O(nlogn)其中 n 是数组中的元素数量。排序的时间复杂度是 O(nlogn)双指针遍历的时间复杂度是 O(n)。空间复杂度O(n)我们需要一个额外的数组来存储元素和它们的索引。 这种方法在空间复杂度上与哈希表方法相同但时间复杂度稍高因为它需要排序。然而这种方法在不允许修改原数组或需要保持元素原始顺序的情况下可能更有用。
暴力法
使用两个嵌套循环遍历数组中的所有元素对。对于每一对元素检查它们的和是否等于目标和。如果找到一对元素的和等于目标和返回这两个元素的索引。 这种方法的时间复杂度是 O(n^2)因为它需要对数组中的每一对元素进行一次检查。
Go语言实现 - 暴力法
package main
func twoSum(nums []int, target int) []int {for i : 0; i len(nums); i {for j : i 1; j len(nums); j {if nums[i] nums[j] target {return []int{i, j}}}}return nil
}C
#include vectorclass Solution {
public:std::vectorint twoSum(std::vectorint nums, int target) {for (int i 0; i nums.size(); i) {for (int j i 1; j nums.size(); j) {if (nums[i] nums[j] target) {return {i, j};}}}return {};}
};算法分析
时间复杂度O(n^2)其中 n 是数组中的元素数量。最坏的情况下我们需要遍历每个元素与其他元素的组合。空间复杂度O(1)我们只需要常数级别的额外空间来存储索引。 暴力法是一种简单直接的方法但是对于大型数据集来说它的效率不高。在实际应用中通常会优先考虑使用哈希表或排序和双指针法来解决这类问题。
二分搜索法
首先对数组进行排序并创建一个新数组来保存排序后元素的原始索引。对于数组中的每个元素使用二分搜索查找 target - nums[i]。如果找到确保两个元素的原始索引不同然后返回它们的原始索引。 这种方法的关键在于排序后我们可以使用二分搜索高效地找到第二个数。
Go语言实现 - 二分搜索法
package main
import (sort
)
func twoSum(nums []int, target int) []int {indexes : make([]int, len(nums))for i : range nums {indexes[i] i}sort.Slice(indexes, func(i, j int) bool {return nums[indexes[i]] nums[indexes[j]]})for i : 0; i len(nums); i {left, right : i1, len(nums)-1complement : target - nums[indexes[i]]for left right {mid : left (right-left)/2if nums[indexes[mid]] complement {return []int{indexes[i], indexes[mid]}} else if nums[indexes[mid]] complement {left mid 1} else {right mid - 1}}}return nil
}C
#include vector
#include algorithm
#include numericclass Solution {
public:std::vectorint twoSum(std::vectorint nums, int target) {std::vectorint indexes(nums.size());std::iota(indexes.begin(), indexes.end(), 0);std::sort(indexes.begin(), indexes.end(), [nums](int i, int j) { return nums[i] nums[j]; });for (int i 0; i nums.size(); i) {int left i 1, right nums.size() - 1;int complement target - nums[indexes[i]];while (left right) {int mid left (right - left) / 2;if (nums[indexes[mid]] complement) {return {indexes[i], indexes[mid]};} else if (nums[indexes[mid]] complement) {left mid 1;} else {right mid - 1;}}}return {};}
};
算法分析
时间复杂度O(nlogn)其中 n 是数组中的元素数量。排序的时间复杂度是 O(nlogn)二分搜索的时间复杂度是 O(logn)总共进行了 n 次二分搜索。空间复杂度O(n)我们需要一个额外的数组来保存索引。 二分搜索法在空间复杂度上与哈希表方法相同但时间复杂度稍高因为它需要排序。这种方法在不允许修改原数组或需要保持元素原始顺序的情况下可能更有用。然而对于两数之和这个问题哈希表法通常是更优的选择因为它的时间复杂度更低。
C的实现
