题目

方法一：暴力枚举

思路和算法

暴力枚举数组中每一个数x，寻找数组中是否存在target-x
c++:

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++){
                       if(nums[i]+nums[j] == target){
                          return {i,j};
                       }
                }
            }
             return {};
    }
};

java:

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[i]+nums[j] == target){
                          return new int[]{i,j};
                       }
                }
        }
        //返回一个长度为0的数组
        return new int[0];
    }
}

复杂度分析

• 时间复杂度：O(n^2),其中n是数组中的元素数量，最坏情况下数组中的任意两个数都要被匹配一下
• 空间复杂度O(1).

方法二：哈希

思路和算法

注意方法一中查找target-x的复杂度过高，因此我们可以用哈希表存储值和下标的对应关系，将复杂度降为O(1)

c++:

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

java

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

复杂度分析

• 时间复杂度：O(n),其中n是数组中的元素数量,对于每一个x，我们可以O(1)的寻找target-x
• 空间复杂度O(1)