LeetCode—— 两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

一、CPP暴力解法

解题思路：由于数组只有一个target，直接简单暴力进行双重循环，记录i，j即为两个数的下标。return {}是C++ 11 的写法，返回的是一个vector数组。
时间复杂度：O(n²)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i,j;
        for(i=0;i<nums.size()-1;i++)
        {
            for(j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                {
                    return {i,j};
                }
            }
        }
        return {i,j};
    }
};

二、使用CPP map

解题思路：

• 使用哈希表记录出现过的数字下标，节约查询时间。
• 当a + b == target时，a == target - b。
• 遍历数组，当前数字为b，如果哈希表中存在 a == target - b，返回 a 和 b 的下标。
• vector<int> 有列表初始化方法，return {index_of_a, index_of_b} 减少代码长度。

首先，创建一个不排序的map，然后遍历数组，使用dict.count统计key的次数：

• 如果返回值是0就说明还没有与之匹配的数，这时，就把dict[nums[i]] 赋值为i。
• 如果存在与之匹配的数，直接返回target - nums[i]和i在字典中的下标。

注意：dict[target - nums[i]]是要找数的索引，i是遍历数的索引。

时间复杂度：O(n)。只需要遍历一遍数组

class Solution {
public:
    vector<int> twoSum(const vector<int>& nums, const int target) {
        unordered_map<int, int> dict;
        for (int i = 0; i < nums.size(); i++)
            //dict.count也可以使用dict.find()
            if (dict.count(target - nums[i]))
                return {dict[target - nums[i]], i};
            else
                dict[nums[i]] = i;
        //如果找不到
        return {0, 0};
    }
};

补充知识点：unordered_map是一个关联容器，其中的元素根据键来引用，而不是根据索引来引用。使用时，必须include unordered_map。在内部，std::unordered_map中的元素不会根据其键值或映射值按任何特定顺序排序，而是根据其哈希值组织到桶中，以允许通过键值直接快速访问各个元素（常量的平均时间复杂度）。并且，std::unorederd_map中的元素的键是唯一的。

三、Java map （同二）

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");
    }
}

注意:java 获取数组大小的方法为length()， return new int[] { map.get(complement), i };是类似于匿名函数的写法，直接返回一个数组对象

三、Python dict （同二）

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}

        for i in range(0,len(nums)):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            dict[target - nums[i]] = i

        return [0, 0]

四、各语言及算法时间复杂度

各语言及算法时间复杂度