Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
这个题目编程之美上面也提到了,不过这里的要求是要返回值在序列中的索引
解法一:
借助于哈希表,时间复杂度为O(n),空间复杂度最坏情况下O(n),代码是java语言
public static int[] twoSumByHash(int[] numbers, int target){ if(numbers == null || numbers.length < 2){ return new int[]{-1,-1}; } Map<Integer,Integer> map = new HashMap<Integer,Integer>(); map.put(target - numbers[0], 0); for(int i=1;i<numbers.length;i++){ if(map.keySet().contains(numbers[i])){ return new int[]{map.get(numbers[i])+1,i+1}; }else{ map.put(target - numbers[i], i); } } return new int[]{-1,-1}; }
解法二:
先排序,然后从两头遍历,时间复杂度为O(n)
public static int[] twoSum(int[] numbers, int target) { int[] nums = numbers.clone(); Arrays.sort(numbers); int i = 0; int j = numbers.length - 1; while(i<j){ if(numbers[i] + numbers[j] == target){ break; }else if (numbers[i] + numbers[j] < target){ i++; }else{ j--; } } if(i< j ){ int[] result = new int[2]; int count = 0; for(int k=0;k<nums.length;k++){ if(nums[k] == numbers[i] || nums[k] == numbers[j]){ result[count++]=k+1; } } return result; } return new int[]{-1,-1}; }
相关推荐
判断青蛙过河leetcode 目录 leetcode 打印不重复元素 √ 4、二维数组中查找目标值(从...一个整数分解成两个质数和 √ 数据分类(int转16进制) √ 设计模式 util doc 基础扎实全面:编程语言、数据结构、算法等 高质量代
答案CTCI书籍和Leetcode问题的解决方案 类别 名称 问题 回答 笔记 个人评分 细绳 是独特的 CTCI 1-1 + 细绳 检查排列 CTCI 1-2 + :star: 细绳 网址化 CTCI 1-3 + 细绳 Penidrom 排列 CTCI 1-4 —— :star: 细绳 一走...
问题:最长公共前缀编写一个函数来查找字符串数组中最长的公共前缀字符串。 ###a13 问题:罗马到整数给定一个罗马数字,将其转换为整数。 输入保证在 1 到 3999 的范围内。 ###a12 问题:整数转罗马|| 给定一个整数...
leetcode 285 leetcode ID problem 难度 使用语言 思路 提交次数 WA点 ...两数之和 ...两数相加 ...三数之和 ...合并两个有序链表 ...两数相除(不使用乘法除法) ...用被除数不断减去除数直至被减数为负(TLE),每次将...在排序数组中查
1:最直接的方式直接双层遍历该数组,找到两个数相加等于该结果。时间复杂度为O(n^2 )。该方法的变种就是遍历一次数组,然后在该数组中搜索target-x是否存在。但是时间复杂度都是O(n^2 ),空间复杂度是T(n) 2:利用...
:计算数组中每对两个元素的总和。 对于每个 twoSum i ,检查是否存在另一个 twoSum j ,其中i + j = target 。 AddBinary :简单的问题。 AddTwoNumbers :简单的问题。 Anagrams :简单的#hashtable问题。 ...
右翼问题总结如下:给定一个整数数组,其值小于或等于所述数组的长度,你如何判断从位置 0 开始的标记是否有可能到达数组的最后一个位置?大批? 标记可以向两个方向移动:向左或向右。 位移是存储在标记当前“站立...
残酷:两个循环或签in def isUnique ( self , astr ): for i in range ( len ( astr )): if astr [ i ] in astr [ i + 1 :]: return False return True astr[i] in astr[i+1:]检查astr[i] in astr[i+1:]也在引擎盖下...
即只关心正负而不关心数值,可以将一个正数数组原地作为一个布尔数组使用。关心的信息的维度不同,可以让一个数组包含多个维度的信息。 Problem42 of LeetCode 题目:给定 n 个非负整数表示每个宽度为 1 的柱子的...
一次遍历两个链表一个节点。 使用sum和carry来跟踪当前的计算 创建新node以存储新sum并添加到新总和链表 如果可用,移动到下一个node 复杂 运行时复杂度O(n) ,假设 n 是较长列表的长度 存储输出列表的空间复杂度为O...
lru cache leetcode LeetCode Fight for a better life. <<<<<<< HEAD 231 easy ...problem, ...problem, ...problem ...(也可以用一维数组,贪心) ...数组: ...用好标记数组: ...两个链表:
leetcode怎么计算空间复杂度是...题型二:动态规划(要整理搜索和DP的区别,都可以用一个状态转移公式F(n)表示) 053:最大字串之和 121:同上 123:同上 091:Decode Ways 简单的一维DP,用额外数组O(n)即可。 139,1
寻找两个有序数组的中位数 困难 Algorithm 5 最长回文子串 中等 Algorithm 6 Z字形变换 中等 Algorithm 7 整数翻转 简单 Algorithm 8 字符串转换整数 (atoi) 中等 Algorithm 9 回文数 简单 Algorithm 10 正则表达式...
153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 155 分钟堆栈,173 二进制搜索树迭代器,HARD:146-LRU 缓存,621-任务调度器,电话号码的 17 个字母组合,HARD:297-序列化和反序列化二叉树,341-...
这是问题的资源: 两个总和-https //www.studytonight.com/post/leetcode-solution-2-sum-problem 加两个数字-https v LBVsXSMOIk4 最长子串,不包含重复字符-https 反向整数-https v EtuWmKsyAZE Palindrom...
第 296 章统计数据 统计数据 554/660 已解决 - 简单 164 中等 ...奇怪的东西,添加685....我发现leetcode会在发布几天后锁定一些问题数字提交...数组中两个数字的最大异或 相同的策略 327, 363, 523, 525 一一构建 dp 312,
DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗...
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。 s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 2.4 Knapsack Problem 给定一个由正整数...
lru缓存leetcode 力码解决方案 Leetcode 是您可以通过解决问题来练习理解常见计算机科学算法和数据结构的网站之一。 在这个存储库中,我存储了迄今为止我在 ...两个指针 () () () () 学分 挑战已解决 :red_heart: 经过
两个链表的交集 0148 排序表 AY 0162 寻找峰值元素 0179 最大数 星期日 0131 回文分区 0108 将有序数组转换为二叉搜索树 第 9 周问题列表: 杰森 0277 找名人 0136 单号 GG 0101 对称树 0329 矩阵中最长的递增路径 ...