[Leetcode][Python/Java]两数之和 Two Sum/两数之和 II - 输入有序数组 Two Sum II
[Leetcode][Python/Java]两数之和 Two Sum/两数之和 II - 输入有序数组 Two Sum II
两数之和 Two Sum
题目大意
https://leetcode-cn.com/problems/two-sum/solution/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解题思路
方法一：暴力法
暴力法很简单。遍历每个元素 x，并查找是否存在一个值与 target - x相等的目标元素。
复杂度分析：
- 时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)的时间。因此时间复杂度为 O(n^2)
- 空间复杂度：O(1)。
方法二：哈希表
复杂度分析：
- 时间复杂度：O(n)， 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
- 空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
利用字典idxDict保存数字num到其下标idx的映射。遍历查找数字num与目标数target的“互补数”时只需查找idxDict[target - num]是否存在即可。
注意：字典的key是target - num或num都可以
Python
转载自书影博客
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
idxDict = dict()
for idx, num in enumerate(nums):
if target - num in idxDict:
return [idxDict[target - num], idx]
idxDict[num] = idxclass Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_dict = {}
for i, num in enumerate(nums):
if num not in num_dict:
num_dict[target - num] = i
else:
return num_dict[num], iJava
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (map.containsKey(nums[i])) {
return new int[]{map.get(nums[i]), i};
}
map.put(target - nums[i], i);
}
return null;
}
}两数之和 II - 输入有序数组 Two Sum II
题目大意
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
与上面一题唯一的不同就是给的数组是排好序的。
解题思路
方法一：哈希存储
同上
方法二：双指针
时间复杂度： O(nlogn)
用两个变量指向数组的开头和结尾：分别指向nums[0]和nums[numsSize];因为已经进行过排序，如果nums[low]+nums[high] < target，则说明low指向的数太小，需要往后移动；反之，则是high指向的数太大，需要前移，当两者相等，遍历结束 。
Python
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
tmp = nums[left] + nums[right]
if tmp > target:
right -= 1
elif tmp < target:
left += 1
else:
return [left+1, right+1]Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int len = nums.length;
int sum;
int left = 0;
int right = len - 1;
while(left < right){
sum = nums[left] + nums[right];
if(sum == target)
return new int[]{left+1, right+1};
else if (sum < target)
left ++;
else
right --;
}
return null;
}
}总结
主要还是学习双指针（已排好序）和哈希表方法，重点是哈希表！
补充：关于Python的enumerate()的用法
看如下代码：
a = [3,4,5,6]
for i, num in a:
print(i, num)输出报错：
TypeError: 'int' object is not iterable
a = [3,4,5,6]
for i, num in enumerate(a):
print(i, num)输出：
(0, 3)
(1, 4)
(2, 5)
(3, 6)补充：关于Python的listname.index(value)
根据值查找索引号
补充：关于Python的listname.count(x)
根据值查找值出现的数量