力扣刷题记录：1、Two Sum

记录LeetCode刷题第一题

本文中包含C++两种方法的题解以及Java和Python的题解

题目描述如下： Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly one solution, and you may not use the same element twice.You can return the answer in any order.

来源：LeetCode

思路： 看到这题首先想到的就是双for循环暴力求解的方法，试了一下也很快做出来了(注意i!=j，即不能加两个同样的数)。但是时间复杂度为O(n^2)，属实有点拉，代码如下：

注意要j!=i，不能加两个相同的数

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

思考了一下，发现这样的两次遍历会将两数相加计算两遍，比如i=0,j=1时计算了nums[0]+nums[1]，而i=1,j=0时，也计算了nums[0]+nums[1]，这样显然是不够好的，因此可以让j从i+1开始遍历，这样就避免了重复计算。代码如下:

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

---

这样的方法运行时间为352ms，显然还是不够好的，有没有更好的方法呢？第一个遍历的for循环显然是少不了的，因此考虑对第二个查找的for循环进行优化。由于本人水平比较拉，对哈希表等数据结构了解的不够深，因此去参考了别人的题解，运用哈希表优化了代码，优化后的代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int> Hashtb;
        for(int i = 0; i < nums.size(); i++){
            auto it = Hashtb.find(target - nums[i]);
            //如果找不到，it会等于哈希表的尾指针
            if(it != Hashtb.end()){
                return {it->second,i};
                //返回键值是it->first
                //返回键对应元素值是it->second
            }
            Hashtb[nums[i]] = i;
        }
        return {};
    }
};

这里只进行了n次循环，由于哈希表的查找 *** 作时间复杂度为O(1)，这样就将第二个查找 *** 作的时间复杂度降到了O(1)，因此此方法的时间复杂度为O(n)。思路是在以nums[i]为键，以i为值的哈希表中寻找和nums[i]相加等于target的数，如果找不到，就把当前数据放入哈希表(这样可以被后续元素查找到)，此方法也能保证不加两个相同的数。

---

题解到这里，Java和Python的思路也与C++一致，只不过Python中用的是字典来模拟哈希表进行查找 *** 作。代码如下：

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
    	Map<Integer, Integer> Hashtb = new HashMap<Integer, Integer>();
    	for(int i = 0; i < nums.length; ++i) {
    		if(Hashtb.containsKey(target - nums[i])) {
    			int[] ans = {Hashtb.get(target - num[i]), i};
    			return ans;
    		}
    		Hashtb.put(nums[i], i);
    	}
    	int[] noans = new int[0];
    	return noans;
    }
}

---

Python

class Solution(object):
    def twoSum(self, nums, target):
    	Hashtb = {}
    	for i,num in enumerate(nums):
    		want = target - num
    		if want in Hashtb:
    			return[Hashtb[want], i]
    		Hashtb[num] = i
    	return []