关关的刷题日记11——Leetcode 1. Two Sum 方法2、3

 点击上方“专知”关注获取更多AI知识!

关小刷刷题11 – Leetcode 1. Two Sum 方法2、3

方法2

方法2:先将数组进行排序,设置两个左右指针,若sum>target, 那么右指针左移,sum<target, 左指针右移。sum=target,对应元素的头尾指针就是所求结果。但是有个问题是这时候得到的头尾指针是元素排序后对应的头尾指针,咱们想求的是元素排序前对应的头尾指针,所以一开始要把原来的数组拷贝一份,然后遍历数组,找到对应下标值。时间复杂度为O(nlogn)的方法,还用了额外空间,貌似也不是很好的方法,但是如果数组已经排好序了这种方法就很赞。

class Solution {
public:
   vector<int> twoSum(vector<int>& nums, int target) {
       vector<int>output;
       vector<int>temp=nums;
       sort(nums.begin(), nums.end());
       int a=0, b=0;
       for(int i=0, j=nums.size()-1; i<j;)
       {
           if(nums[i]+nums[j]>target)
               j--;
           else if(nums[i]+nums[j]<target)
               i++;
           else
           {
               a=nums[i];
               b=nums[j];
               break;
           }
       }
       for(int i=0; i<temp.size(); i++)
       {
           if(temp[i]==a || temp[i]==b)
               output.push_back(i);
       }
       return output;
   }
};

方法3

方法3:用哈希表,key存数组元素,value存对应的下标值,遍历数组,当查找到target-nums[i]时,此时元素的下标和target-nums[i]的value值就是所求结果。时间复杂度为O (n)的方法,用了额外空间。

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

保护好自己,成为更好的人,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。




-END-


欢迎使用专知

专知,一个新的认知方式!目前聚焦在人工智能领域为AI从业者提供专业可信的知识分发服务, 包括主题定制、主题链路、搜索发现等服务,帮你又好又快找到所需知识。


使用方法>>访问www.zhuanzhi.ai, 或点击文章下方“阅读原文”即可访问专知


中国科学院自动化研究所专知团队

@2017 专知


专 · 知


关注我们的公众号,获取最新关于专知以及人工智能的资讯、技术、算法、深度干货等内容。扫一扫下方关注我们的微信公众号。


点击“ 阅读原文 ”,使用 专知!
展开全文
Top
微信扫码咨询专知VIP会员