文档章节

leetcode-two sum

梦想游戏人
 梦想游戏人
发布于 2016/07/14 01:03
字数 295
阅读 15
收藏 0

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

 

常规方法肯定超时,所以用查表来解决,但是提交后发现ERROR 因为测试数据可能是负数,所以换成map


class Solution1 {
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		static int cache[99999] = { -1 };//缓存数字 该数字可能重复值

		for (int i = 0; i < 99999; i++)
		{
			cache[i] = -1;
		}
		static vector<int> cache1[99999];//缓存该数字的index

		for (int i = 0; i < nums.size(); i++)
		{
			cache[i] = nums[i];
			int index = nums[i];
			auto &v = cache1[index];

			v.push_back(i);
	

		}


		int x = 0, y = 0;


		for (int i = 0; i < nums.size(); i++)
		{
			int delta = target - nums[i];
			if (delta < 0)continue;
			if (cache1[delta].size() == 0)continue;
			if (cache1[nums[i]].size() == 0)continue;
			x = cache1[delta][0];
			int ii = 0;
			if (cache1[delta].size() != 1)ii = 1;

			for (; ii < cache1[delta].size(); ii++)
			{


				if (cache1[delta][ii] != 0)
				{

					y = cache1[nums[i]][ii];



					if (x > y) return{ y, x };


					return{ x, y };
				}
			}

		}
		return{ -1, -1 };
	}
};

 

 


class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target)
	{
		std::map<int, int>m;
		for (int i = 0; i < nums.size(); i++)
		{
			m[nums[i]] = i;//缓存 数字的index
		}

		for (int i = 0; i < nums.size(); i++)
		{
			int delta = target - nums[i];
			auto res= m[delta];
		
			if (res!=0)
			{
				return{ i, res};
			}
		}


	}
};

 

© 著作权归作者所有

共有 人打赏支持
下一篇: pomelo连接redis
梦想游戏人
粉丝 37
博文 444
码字总数 127453
作品 0
成都
私信 提问
leetcode题解(二叉树和递归问题)

这篇博客我们主要来看二叉树和二叉树问题中使用递归来解决问题的思路。这类问题有时思路很简单,这是因为二叉树具有天然的递归结构,所以我们使用递归的解法解决二叉树有关的问题就变得非常明...

吴小琪
2018/06/26
0
0
Leetcode_Problem 16_3 Sum Closest

题目 问题网址: https://leetcode.com/problems/3sum-closest/description/ 问题描述: Given an array S of n integers, find three integers in S such that the sum is closest to a giv......

quiet_girl
2018/03/09
0
0
LeetCode 64. Minimum Path Sum

原题 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only mov......

dby_freedom
2018/10/11
0
0
[算法][LeetCode] Dynamic Programming(DP)动态规划

极值的问题一般考虑用DP [LeetCode] Coin Change 硬币找零 http://www.cnblogs.com/grandyang/p/5138186.html [LeetCode] Coin Change 2 硬币找零之二 http://www.cnblogs.com/grandyang/p/7......

素雷
2017/10/19
0
0
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
53
0

没有更多内容

加载失败,请刷新页面

加载更多

linux 扩展lv

相关概念 逻辑卷可以实现硬盘空间的动态划分和管理。 1】 物理卷 LV 处于最低层,可以是物理硬盘上的分区,也可以是整个物理硬盘 2】 卷组 VG 卷组建立在物理卷之上,一个卷组至少要包括一个...

hnairdb
4分钟前
0
0
如何快速定位Ruby函数源码

如何快速定位Ruby函数源码 1、gem gem which sidekiq 2、bundle bundle show redis 3、CTags Sublime extend ActiveSupport::Concernrescue_fromcurrent_company.cc_ad_tasks.creat......

mingle
5分钟前
0
0
基于 DataLakeAnalytics 的数据湖实践

随着软硬件各方面条件的成熟,数据湖(Data Lake)已经越来越受到各大企业的青睐, 与传统的数仓实践不一样的是,数据湖不需要专门的“入仓”的过程,数据在哪里,我们就从哪里读取数据进行分析...

阿里云云栖社区
6分钟前
0
0
word文档处理成富文本生成sql语句导入mysql

问题:需要将大量的已存在的word文档导入到web项目里在网站展示,不可能通过编辑录入的方式处理,通过程序实现。 解决思路:通过读取word文档处理成html,再获取html富文本内容,拼接成sql,...

S三少S
13分钟前
29
0
WAF开放规则定义权:专家策略+用户自定义策略=Web安全

在第一期“漫说安全”栏目中,我们用四格漫画的形式介绍了基于深度学习的阿里云WAF到底智能在哪里,能帮客户解决什么问题。 在今天的这期栏目里,我们依然通过漫画这种通俗易懂的方式,与大家...

迷你芊宝宝
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部