两数之和 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] = 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/

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 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)

根据值查找值出现的数量