Array Algorithm 1

1435-郭同学

发表文章数:18

热门标签

, , ,
首页 » 算法 » 正文

算法刷题系列 Algorithm


Difficulty:easy

Two Number Sum

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.
Note that the target sum has to be obtained by summing two di!erent integers in the array; you can’t add a single integer to itself in order to obtain the target sum.
You can assume that there will be at most one pair of numbers summing up to the target sum.

Array Algorithm 1
Solution 1:
time complexity : O(n^2)

def twoNumberSum(array, targetSum):
    # Write your code here.
	solution = []
    for i in range(len(array) - 1):
		currentNum = array[i]
		for j in range(i + 1,len(array)):
			secondNum = array[j]
			if currentNum + secondNum == targetSum:
				if currentNum > secondNum:
					return [secondNum, currentNum]
				else:
					return [currentNum, secondNum]
	return []

Solution 2:
Hashing
time complexity : O(n)

def twoNumberSum(array, targetSum):
    nums = {}
	for num in array:
		if targetSum - num in nums:
			return [targetSum - num, num]
		else:
			nums[num] = True
	return []

Solution 3:
Sort
time complexity : O(nlogn)

def twoNumberSum(array, targetSum):
    array.sort()
	left = 0
	right = len(array) - 1
	while left < right:
		currentSum = array[left] + array[right]
		if currentSum == targetSum:
			return [array[left], array[right]]
		elif currentSum > targetSum:
			right -= 1
		else:
			left += 1
	return []

from AlgoExpert

未经允许不得转载:作者:1435-郭同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Array Algorithm 1》 发布于2021-02-06

分享到:
赞(1) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录