题目地址
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
题目描述
这是leetcode头号题目two sum
的第二个版本,难度简单。
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
思路
由于题目没有对空间复杂度有求,用一个hashmap 存储已经访问过的数字即可。
假如题目空间复杂度有要求,由于数组是有序的,只需要双指针即可。一个left指针,一个right指针,
如果left + right 值 大于target 则 right左移动, 否则left右移,代码见下方python code。
如果数组无序,需要先排序(从这里也可以看出排序是多么重要的操作)
关键点解析
无
代码
- 语言支持:JS,Python
Javascript Code:
/* * @lc app=leetcode id=167 lang=javascript * * [167] Two Sum II - Input array is sorted * * https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ * * algorithms * Easy (49.46%) * Total Accepted: 221.8K * Total Submissions: 447K * Testcase Example: '[2,7,11,15]\n9' * * Given an array of integers that is already sorted in ascending order, find * two numbers such that they add up to a specific target number. * * The function twoSum should return indices of the two numbers such that they * add up to the target, where index1 must be less than index2. * * Note: * * * Your returned answers (both index1 and index2) are not zero-based. * You may assume that each input would have exactly one solution and you may * not use the same element twice. * * * Example: * * * Input: numbers = [2,7,11,15], target = 9 * Output: [1,2] * Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2. * */ /** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function(numbers, target) { const visited = {} // 记录出现的数字, 空间复杂度N for (let index = 0; index < numbers.length; index++) { const element = numbers[index]; if (visited[target - element] !== void 0) { return [visited[target - element], index + 1] } visited[element] = index + 1; } return []; };
Python Code:
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: visited = {} for index, number in enumerate(numbers): if target - number in visited: return [visited[target-number], index+1] else: visited[number] = index + 1 # 双指针思路实现 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: left, right = 0, len(numbers) - 1 while left < right: if numbers[left] + numbers[right] < target: left += 1 if numbers[left] + numbers[right] > target: right -= 1 if numbers[left] + numbers[right] == target: return [left+1, right+1]LeetCode题解124.binary-tree-maximum-path-sum
题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…
LeetCode题解113.path-sum-ii题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…
LeetCode题解15.3-sum题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…
LeetCode题解1186.maximum-subarray-sum-with-one-deletion题目地址 https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ 题目描述 给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。 换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素(只能删一次哦)…
LeetCode题解129.sum-root-to-leaf-numbers题目地址 https://leetcode.com/problems/sum-root-to-leaf-numbers/description/ 题目描述 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. …