讨论/《腾讯》 - 两数之和/
《腾讯》 - 两数之和
共 5 个回复

1,暴力破解法

就是使用两个for循环,这种效率很差

    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++)
                if (nums[i] + nums[j] == target)
                    return new int[]{i, j};
        }
        return new int[]{-1, -1};
    }


2,使用HashMap解决

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


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

6
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
     //遍历nums 当发现 (target- nums[i]) in hash table  break
    // 否则 hash_table.push(nums[i])
      std::unordered_map<int,int> tmap;
      int i=0;
      for(  i=0;i<nums.size();i++)
      { 
        //  std::cout<< i ;
          if(tmap.count(target- nums[i] )) 
          {
              //std::cout<< i ;
              break;
          }else
          {
              tmap.emplace(nums[i],i);
          }
      }
     if( i==nums.size()) return {};
      auto it= tmap.find(target- nums[i]);
      return vector<int>{i,it->second};
    }
};
3

看着map的答案,试了好久,Map的赋值为什么不放在取值判断的前面。这样可以有效的避免一种,target是本身两倍的情况。

1

一遍遍历+哈希
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> resMap;
for(int i=0;i< nums.size();i++)
{
int n = nums[i];
if(resMap[target-n] != 0 && resMap[target-n] != (i+1))
{
return {i,resMap[target-n]-1};
}else{
resMap[n] = i+1;
}

    }

    return {};
}

};

双指针