LeetCode 1

小鱼儿 2021-12-21 10:15 165阅读 0赞

问题描述：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

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

解法一：暴力破解

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> Tsum(2,0);
            for(int i =0;i<nums.size();i++){
                for(int j=i+1;j<nums.size();j++){
                    if(nums[i]+nums[j]==target){
                        Tsum[0] = i;
                        Tsum[1] = j;
                    }
                }
            }
            return Tsum;
        }
    };

采用这个方法时间复杂度是O(N^2)，空间复杂度是O(1)

解法二：哈希表

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> Tsum(2,0);
            map<int, int> Msum;
            for(int i = 0;i<nums.size();i++){
                Msum[nums[i]] = i;
            }
            map<int, int>::iterator iter;  
            for(int i = 0;i<nums.size();i++){
                int c = target - nums[i];
                iter = Msum.find(c);
                if(iter != Msum.end()&& iter->second!=i){
                    Tsum[0] = i;
                    Tsum[1] = iter->second;
                }
            }
            return Tsum;
        }
    };

采用这个方法时间复杂度是O(N)，空间复杂度是O(N)

发表评论取消回复

表情：

评论列表（有 0 条评论，165人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode Solution-1

1. Two Sum Given an array of integers, return indices of the two numbers such tha

蔚落/ 2023年08月17日 17:45/ 0 赞/ 121 阅读

相关 Leetcode（1 、2）

1.两数求和思路：类似排序的思想，有点概率论的感觉，优化一般先找第一个的所有搭配然后第二个数就可以从第二个数开始找以此类推比全部找省点时间 /

淩亂°似流年/ 2023年08月17日 16:20/ 0 赞/ 104 阅读

相关 leetcode1-100

文章目录重做 1.两数之和(hash) find的时间复杂度 2. 两数相加(链表) 3. 无重复字符的最长子串（滑动窗口双指针）

ゝ一世哀愁。/ 2023年07月13日 03:09/ 0 赞/ 9 阅读

相关 leetcode No.1

Leetcode No.1 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6

桃扇骨/ 2023年01月09日 15:36/ 0 赞/ 106 阅读

相关 leetcode1

前言：研一了，提前刷刷leetcode，为以后找工作打基础。题意：在数组中找出两个数相加为target，并返回这两个数的索引要求： 1.索引小的在前

柔情只为你懂/ 2022年08月05日 11:26/ 0 赞/ 95 阅读

相关二刷 leetcode（1）

26. 删除排序数组中的重复项给定一个排序数组，你需要在[原地][Link 1]删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空

叁歲伎倆/ 2022年05月21日 08:43/ 0 赞/ 153 阅读

相关 leetcode（1）

目录 2.整数反转 3.回文数 4罗马数字转整型 5.最长公共前缀 6.有效的括号 7.合并两个有序的链表 8.删除有序数组中的重复元素 9.括号生成 10.

柔光的暖阳◎/ 2022年03月09日 01:10/ 0 赞/ 115 阅读

相关 ARTS LeetCode1 TwoSum

two Sum Given an array of integers, return indices of the two numbers such that they ad

傷城~/ 2022年03月01日 21:16/ 0 赞/ 226 阅读

相关 LeetCode 1

问题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案

小鱼儿/ 2021年12月21日 10:15/ 0 赞/ 166 阅读

相关 Leetcode 1 two-sum

class Solution { public int[] twoSum(int[] nums, int target) {

ゞ浴缸里的玫瑰/ 2021年10月18日 10:46/ 0 赞/ 241 阅读