LeetCode 1

小鱼儿 2021-12-21 10:15 152阅读 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 条评论，152人围观）

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

相关阅读

相关 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 赞/ 111 阅读

相关 Leetcode（1 、2）

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

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

相关 leetcode No.1

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

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

相关 Leetcode - t1 - java

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

约定不等于承诺〃/ 2022年11月21日 11:35/ 0 赞/ 156 阅读

相关 leetcode1

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

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

相关 [leetcode]: 1. Two Sum

1.题目 Given an array of integers, return indices of the two numbers such that they add

刺骨的言语ヽ痛彻心扉/ 2022年06月15日 12:06/ 0 赞/ 193 阅读

相关 leetcode（1）

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

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

相关 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 赞/ 194 阅读

相关 LeetCode 1

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

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

相关 LeetCode：课程表 (1, 2)

LeetCode：课程表1 这是很简单的拓扑排序问题现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。例如，想要学

￡神魔★判官ぃ/ 2021年12月04日 01:34/ 0 赞/ 230 阅读