下载APP
登录
关闭
讲堂
算法训练营
Python 进阶训练营
企业服务
极客商城
客户端下载
兑换中心
渠道合作
推荐作者
当前播放: 15 | 面试题:两数之和
00:00 / 00:00
标清
  • 标清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看

算法面试通关40讲

共62讲 · 62课时·约600分钟
18863
免费
01 | 合格程序员的第一步:算法...
免费
02 | 如何事半功倍地学习算法与...
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算...
免费
05 | 理论讲解:数组&链表
06 | 面试题:反转一个单链表&...
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是...
09 | 面试题:用队列实现栈&用...
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第...
12 | 面试题:返回滑动窗口中的...
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二...
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索...
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时...
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最...
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方...
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词...
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&...
42 | 面试题:N皇后问题的另一...
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径...
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友...
54 | 面试题:岛屿的个数&朋友...
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LR...
57 | 理论讲解:布隆过滤器
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件...
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契...
62 | 最后的一些经验分享

精选留言(15)

  • 2018-10-29
    set不允许重复。如果是数组是[3,3] target是6,则set是3,所以这里不能用set。
    1
    23
  • 2018-11-01
    因为set的无序 所以在获取第一个数的下标的时候会有问题,所以这里使用set不是很好,不过可以使用map,用来存储下标和数:

    public int[] twoSum(int[] nums, int target) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int[] ans = new int[2];
            for (int i = 0; i < nums.length; i++) {
                int tt = target - nums[i];
                if (map.containsKey(nums[i])) {
                    ans[0] = map.get(nums[i]);
                    ans[1] = i;
                } else {
                    map.put(tt, i);
                }
            }

            return ans;
        }
    展开
    10
  • 2018-10-27
    题目要求返回的是下标,用map好些吧,可以存储下标
    3
  • 2018-10-26
    对于每一个知识点,老师能否举个leetcode上hard的题,谢谢?
    3
  • 2018-12-25
    这个还可以更简单,用Map,key是9-x的值,value是x的下标,开始遍历前map是空的,遍历的同时判断,if(map.get(x)==null){map.put(i)} else return new int[]{i,map.get(x);
    o(n)的时间复杂度
    2
  • 2018-12-17
    难道不是用map更好?
    go版本实现:
    func twoSum(arr []int, target int) [2]int{
        tmpMap := map[int]int{}
        for k, v := range arr{
            if index, ok := tmpMap[target-v]; ok{
                return [2]int{index, k}
            }
            tmpMap[v] = k
        }
        return [2]int{-1,-1}
    }
    展开
    1
  • 2019-10-10
    用Set不合适,改用map的话,key用来记录nums[i]的值,value用来记录对应的下标

    public int[] twoSum(int[] nums, int target) {
            int[] result = new int[2];
            Map<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length ; i++) {
                map.put(nums[i],i);
            }
            for (int i = 0; i < nums.length; i++) {
                int tmp = target - nums[i];
                if(map.containsKey(tmp)&&map.get(tmp)!=i){
                     result[0] = map.get(tmp);
                    result[1] = i;
                }
            }
            return result;
        }
    展开

    作者回复: Cool!

  • 2019-08-21
    private static int[] two_sum_method(int[] nums, int target) {
            Map<Integer, Integer> tempMap = new HashMap<Integer, Integer>();
            for (Integer i = 0; i < nums.length; i++) {
                if (tempMap.get(nums[i]) == null) {
                    tempMap.put(target-nums[i], i);
                } else {
                    return new int[]{i, tempMap.get(i)};
                }
            }
            return null;
        }
    展开

    作者回复: cool!

    1
  • 2019-03-04
    用map 的前提是 不能出现重复的值,比如:{3,3}

    因为map 的k 存的是值,v 存的是下标。
  • 题目里的`exactly one solution`,导致解决的办法,有点粗暴,好比不需要考虑重复,因为重复元素,意味着多个解而已。只需要输出一个。即可。
    感觉还是要仔细读题,难度比easy更easy吧。
  • 2019-01-14
    PHP 暴力解法

    ```
    public function twoSum($nums, $target)
        {
            $outArr = [];
            foreach ($nums as $key => $num) {
                $num1 = $target - $num;
                foreach ($nums as $k => $n) {
                    if ($k != $key) {
                        if ($num1 == $n) {
                            $outArr = [
                                $key,
                                $k,
                            ];
                            if (!empty($outArr)) {
                                return $outArr;
                            }
                        }
                    }

                }
            }
            return $outArr;
        }
    ```
    展开
  • 2019-01-03
    这段代码用了快排,时间复杂度n*logn,但是在leetcode上运行比时间复杂度N的C++快,亲测过,原因是什么?
    public int[] twoSum(int[] nums, int target) {
             if(nums == null)
                 return null;
             int[] nums2 = Arrays.copyOf(nums, nums.length);
             Arrays.sort(nums2);
             int a = 0, b = 0;
             int start = 0, end = nums2.length-1;
             //find two nums
             while(start<end){
                 int sum = nums2[start] + nums2[end];
                 if(sum < target)
                     start++;
                 else if(sum > target)
                     end--;
                 else{
                     a = nums2[start]; b = nums2[end];
                     break;
                 }
             }
             //find the index of two numbers
             int[] res = new int[2];
             for(int i = 0; i < nums.length; i++){
                 if(nums[i] == a){
                     res[0] = i;
                     break;
                 }
             }
             if(a != b){
                 for(int i = 0; i < nums.length; i++){
                     if(nums[i] == b){
                         res[1] = i;
                         break;
                     }
                 }
             } else{
                 for(int i = 0; i < nums.length; i++){
                     if(nums[i] == b && i != res[0]){
                         res[1] = i;
                         break;
                     }
                 }
             }
             
             return res;
         }
    展开
  • 同样的代码,python3里面运行时间是python的3倍??

    作者回复: 可以大概是 leetcode 自己的问题。

  • 2018-10-28
    两个数求和,使用set是否存在些问题,因为set会去重复,同样的元素是指,下角标相同的不可重复使用。map更适用
  • 2018-10-27
    老师,这里边应该用hashmap存入元素的值和其下标吧,因为结果要返回下标