[Leetcode][Python/Java]两数之和 Two Sum/两数之和 II - 输入有序数组 Two Sum II

一时失言乱红尘 2022-06-13 09:27 147阅读 0赞

# 两数之和 Two Sum #

## 题目大意 ##

[https://leetcode-cn.com/problems/two-sum/solution/][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 ####

转载自[书影博客][Link 1]

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] = idx

class 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], i

#### Java ####

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/][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) ###

根据值查找值出现的数量

[https_leetcode-cn.com_problems_two-sum_solution]: https://leetcode-cn.com/problems/two-sum/solution/
[Link 1]: http://bookshadow.com/weblog/2015/02/03/leetcode-two-sum/
[https_leetcode-cn.com_problems_two-sum-ii-input-array-is-sorted]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/