1 Two Sum

Method 1: 双重for循环，判断是否想加等于target 时间复杂度：O(n^2)

Method 2: 使用hash记录已经循环过的值，每次判断target-current O(n)

Python

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(length):
            for j in range(i+1,length):
                if nums[i] + nums[j] == target:
                    return [i,j]

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

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++){
            if(m.find(nums[i]) == m.end())
                m[target - nums[i]] = i;
            else{
                result.push_back(m[nums[i]]);
                result.push_back(i);
                break;
            }
        }
        return result;
    }
};

Java

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);
        }
        return new int[]{-1, -1};
    }
}