Leetcode-001-两数之和

Leecode-001-Two Sum

思路：哈希表

题目描述

给出一个数组和一个两数之和的目标，找到对应目标的数组中两个数的下标。

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution 1：暴力法

• 使用两层循环，外层循环计算当前元素与 target之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标。

Solution 2: 一遍哈希表

• 在进行迭代并将元素插入到列表中的同时，我们还会回过头来看检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应的解，并立即返回。

Java

Solution 1：暴力法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

• 时间复杂度：O(n^2) 对于每个元素，其实遍历了两次数组

• 空间复杂度：O(1)

Solution 2: 一遍哈希表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

• 时间复杂度：O(n) 最差情况下遍历一遍数组
• 空间复杂度：O(n) 最差情况下存整个数组

测试用例：

public static void main(String[] args) {
    Solution solution = new Solution();
    int[] arr = {2, 7, 11, 15};
    System.out.println(Arrays.toString(solution.twoSum(arr,9)));
}

Python

Python版本地址

Solution :利用字典

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        q={}
        for x in range(len(nums)):
            a = target -nums[x]
            if nums[x] in q:
                return q[nums[x]],x
            else:
                q[a] = x

打赏