全球主机交流论坛

标题: 20201217-学好算法，大厂996不是梦-两数之和 [打印本页]
作者: zhubaba2019    时间: 2020-12-17 14:28
标题: 20201217-学好算法，大厂996不是梦-两数之和
来来来，搞搞算法，玩机有个毛意思。

今日一题：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

 

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
作者: 夏生啊    时间: 2020-12-17 14:32
有序吗，有序的话直接双指针扫描，O(n)。无序的话就先排序在扫描
作者: wo284473037    时间: 2020-12-17 14:34
我这高数渣渣让了，让了
作者: zhubaba2019    时间: 2020-12-17 14:36
夏生啊 发表于 2020-12-17 14:32
有序吗，有序的话直接双指针扫描，O(n)。无序的话就先排序在扫描

无序，时间复杂度要求O(n), 可以借用空间。
作者: niguli5    时间: 2020-12-17 14:43
哈希表，On时间
作者: ingxx    时间: 2020-12-17 14:45
hashMap
作者: ddane    时间: 2020-12-17 14:47
我这高数渣渣让了
作者: yumo    时间: 2020-12-17 14:48
总数减再求哈希
作者: ovo    时间: 2020-12-17 14:51
996太累，不如affman
作者: 8a38a522    时间: 2020-12-17 14:52
写个2 sum还跟我大厂，3 sum会了吗？k sum会了吗？就算了都会了，想要进大厂，leetcode先来200题再说
作者: dragonfsky    时间: 2020-12-17 14:53
现在才开始刷第一题
作者: zdszf    时间: 2020-12-17 14:54
本帖最后由 zdszf 于 2020-12-17 15:04 编辑
  1. nums=(2 7 11 15) && target=9 && for ((i=0;i<${#nums[*]};i++)); do for ((j=$((${#nums[*]}-1));j>=0;j--)); do [[ $((${nums[i]}+${nums[j]})) == $target ]] && [[ ${nums[i]} != ${nums[j]} ]] && echo $i $j && break 2; done; done
复制代码
作者: 三和大神    时间: 2020-12-17 14:54
996太累，不如公务员
作者: zhubaba2019    时间: 2020-12-17 14:54
wo284473037 发表于 2020-12-17 14:34
我这高数渣渣让了，让了

题都是刷出来的，都有套路
作者: zhubaba2019    时间: 2020-12-17 14:55
ovo 发表于 2020-12-17 14:51
996太累，不如affman

affman太内卷我们要去更大的地方内卷。
作者: zhubaba2019    时间: 2020-12-17 14:57
C#题解如下。大佬们不要嘲笑我的代码风格，有其他版本的大佬也可以帖出来

/// <summary>
        /// 这个算法，主要通过字典来判重找出其中的两个数字
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        private int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for(var i = 0; i < nums.Length; i ++)
            {
                //判断字典或者哈希表中是否存在目标-当前数组值，是则返回
                if(dic.ContainsKey(target-nums[i]))
                {
                    return new int[2] { dic[target - nums[i]], i};
                }
                //以值为key，下标为value存入字典或者哈希表
                dic.Add(nums[i], i);
            }
            return null;
        }
作者: zhubaba2019    时间: 2020-12-17 15:02
zdszf 发表于 2020-12-17 14:54

大佬你的这个O(n的平方)了吧
作者: kunkka    时间: 2020-12-17 15:03
这是LeetCode上非常基础的题了，就这小厂都进不去
作者: nmsl    时间: 2020-12-17 15:06
笔试都没这么简单的题，面试手写更不谈，没有机会996
作者: zhubaba2019    时间: 2020-12-17 15:08
nmsl 发表于 2020-12-17 15:06
笔试都没这么简单的题，面试手写更不谈，没有机会996

先从基础的来 从今天开始跟大家每日一道算法题。挑的是微软的哥们给的题库
作者: zdszf    时间: 2020-12-17 15:12
zhubaba2019 发表于 2020-12-17 15:02
大佬你的这个O(n的平方)了吧

学⑤渣 又不是程序员
作者: 可乐呀    时间: 2020-12-17 20:23
  1. class Solution {
  2. private:
  3.     map<int, int > m;
  4.     vector<int> a;
  5. public:
  6.     vector<int> twoSum(vector<int> &nums, int target) {
  7.         for (int i = 0; i < nums.size(); ++i) {
  8.             m[nums[i]] = i;
  9.         }
  10.         for (int i = 0; i < nums.size(); ++i) {
  11.             if (m[target - nums[i]] && (i != m[target - nums[i]])) {
  12.                 a.push_back(i);
  13.                 a.push_back(m[target - nums[i]]);
  14.                 break;
  15.             }
  16.         }
  17.         return a;
  18.     }
  19. };
复制代码




欢迎光临 全球主机交流论坛 (https://lilynana.eu.org/) Powered by Discuz! X3.4