20201217-学好算法，大厂996不是梦-两数之和

zhubaba2019

来来来，搞搞算法，玩机有个毛意思。

今日一题：
给定一个整数数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

8a38a522

写个2 sum还跟我大厂，3 sum会了吗？k sum会了吗？就算了都会了，想要进大厂，leetcode先来200题再说

可乐呀

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. };

复制代码

zdszf

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
   

复制代码

夏生啊

有序吗，有序的话直接双指针扫描，O(n)。无序的话就先排序在扫描

wo284473037

我这高数渣渣让了，让了

zhubaba2019

夏生啊 发表于 2020-12-17 14:32
有序吗，有序的话直接双指针扫描，O(n)。无序的话就先排序在扫描

无序，时间复杂度要求O(n), 可以借用空间。

niguli5

哈希表，On时间

ingxx

hashMap

ddane

我这高数渣渣让了

yumo

总数减再求哈希

ovo

996太累，不如affman