热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[LeetCode]1.TwoSum两数和

Givenanarrayofintegers,returnindicesofthetwonumberssuchthattheyadduptoaspecificta

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, and you may not use the same element twice.

Example:

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

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

给一个没排序的包含整数的数组,找出使得两个数的和是给定值的indices。假设每个输入只有一个答案, 同一元素不会用到两次。

解法:

1. 暴力解法,两个for循环遍历,两个数相加和目标数比较。Time: O(n^2)

2. 先对数组快速排序,然后用两个指针分别指向头和尾,每次比较头尾两个数的和,如果比target小,头标记右移,如果大,尾标记左移。需要注意记录快速排序前后数字的位置变化。Time: O(n)

3. 先遍历一遍数组,建立数字和index的HashMap,然后再遍历一遍,开始查找target - num[i]是否在map中,如果在,找到并返回index。Time: O(n)  Space: O(n)

Java:解法1

public static int[] twoSum(int[] numbers, int target) {
    int[] ret = new int[2];
    for (int i = 0; i  

Java:解法2

class Pair implements Comparable{
    public int number;
    public int idx;
    public Pair(int number, int idx){
        this.number = number;
        this.idx = idx;
    }
    public int compareTo(Pair other){
        return this.number - other.number;
    }
}
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        Pair[] pairs = new Pair[n];
        for(int i = 0; i  target){
                end--;
            }
            else{
                if(pairs[begin].idx > pairs[end].idx){
                    result[0] = pairs[end].idx;
                    result[1] = pairs[begin].idx;
                }else{
                result[0] = pairs[begin].idx;
                result[1] = pairs[end].idx;
                }
                break;
            }
        }
        return result;
    }
}  

Java: 解法3,Two loops

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap m = new HashMap();
        int[] res = new int[2];
        for (int i = 0; i  

Java: 解法3,one loop

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap m = new HashMap();
        int[] res = new int[2];
        for (int i = 0; i  

Python:

class Solution(object):
    def twoSum(self, nums, target):
        hash_map = {}
        for i, v in enumerate(nums):
            hash_map[v] = i

        for index1, value in enumerate(nums):
            if  target - value in hash_map:
                index2 = hash_map[target - value]
                if index1 != index2:
                    return [index1, index2]  

Python:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lookup = {}
        for i, num in enumerate(nums):
            if target - num in lookup:
                return [lookup[target - num], i]
            lookup[num] = i

Python: wo

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lookup = {}
        for i in range(len(nums)):
            if target - nums[i] in lookup:
                return [lookup[target - nums[i]], i]
            lookup[nums[i]] = i  

Python:

class Solution(object):
    def twoSum(self, nums, target):
        if len(nums) <= 1:
            return False
        buff_dict = {}
        for i in range(len(nums)):
            if nums[i] in buff_dict:
                return [buff_dict[nums[i]], i]
            else:
                buff_dict[target - nums[i]] = i

C++:

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map lookup;
        for (int i = 0; i  

  

  

 

相似题目:

[LeetCode] 167. Two Sum II - Input array is sorted 两数和 II - 输入是有序的数组 

[LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 

[LeetCode] 653. Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树

  

All LeetCode Questions List 题目汇总

 

 

 


推荐阅读
  • 个人学习使用:谨慎参考1Client类importcom.thoughtworks.gauge.Step;importcom.thoughtworks.gauge.T ... [详细]
  • JDK源码学习之HashTable(附带面试题)的学习笔记
    本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记,包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货,并附带了其他相关主题的学习笔记。 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • IjustinheritedsomewebpageswhichusesMooTools.IneverusedMooTools.NowIneedtoaddsomef ... [详细]
  • 本文整理了Java面试中常见的问题及相关概念的解析,包括HashMap中为什么重写equals还要重写hashcode、map的分类和常见情况、final关键字的用法、Synchronized和lock的区别、volatile的介绍、Syncronized锁的作用、构造函数和构造函数重载的概念、方法覆盖和方法重载的区别、反射获取和设置对象私有字段的值的方法、通过反射创建对象的方式以及内部类的详解。 ... [详细]
  • EPPlus绘制刻度线的方法及示例代码
    本文介绍了使用EPPlus绘制刻度线的方法,并提供了示例代码。通过ExcelPackage类和List对象,可以实现在Excel中绘制刻度线的功能。具体的方法和示例代码在文章中进行了详细的介绍和演示。 ... [详细]
  • HashMap的相关问题及其底层数据结构和操作流程
    本文介绍了关于HashMap的相关问题,包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题,并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者,本文将为您提供一些有用的技术和经验。 ... [详细]
  • CSS3选择器的使用方法详解,提高Web开发效率和精准度
    本文详细介绍了CSS3新增的选择器方法,包括属性选择器的使用。通过CSS3选择器,可以提高Web开发的效率和精准度,使得查找元素更加方便和快捷。同时,本文还对属性选择器的各种用法进行了详细解释,并给出了相应的代码示例。通过学习本文,读者可以更好地掌握CSS3选择器的使用方法,提升自己的Web开发能力。 ... [详细]
  • 本文讨论了一个关于cuowu类的问题,作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案,并给出了两个可能导致错误的原因。 ... [详细]
  • 本文探讨了C语言中指针的应用与价值,指针在C语言中具有灵活性和可变性,通过指针可以操作系统内存和控制外部I/O端口。文章介绍了指针变量和指针的指向变量的含义和用法,以及判断变量数据类型和指向变量或成员变量的类型的方法。还讨论了指针访问数组元素和下标法数组元素的等价关系,以及指针作为函数参数可以改变主调函数变量的值的特点。此外,文章还提到了指针在动态存储分配、链表创建和相关操作中的应用,以及类成员指针与外部变量的区分方法。通过本文的阐述,读者可以更好地理解和应用C语言中的指针。 ... [详细]
  • 本文详细介绍了Java中vector的使用方法和相关知识,包括vector类的功能、构造方法和使用注意事项。通过使用vector类,可以方便地实现动态数组的功能,并且可以随意插入不同类型的对象,进行查找、插入和删除操作。这篇文章对于需要频繁进行查找、插入和删除操作的情况下,使用vector类是一个很好的选择。 ... [详细]
  • Java学习笔记之面向对象编程(OOP)
    本文介绍了Java学习笔记中的面向对象编程(OOP)内容,包括OOP的三大特性(封装、继承、多态)和五大原则(单一职责原则、开放封闭原则、里式替换原则、依赖倒置原则)。通过学习OOP,可以提高代码复用性、拓展性和安全性。 ... [详细]
  • 开发笔记:Java是如何读取和写入浏览器Cookies的
    篇首语:本文由编程笔记#小编为大家整理,主要介绍了Java是如何读取和写入浏览器Cookies的相关的知识,希望对你有一定的参考价值。首先我 ... [详细]
  • 本文介绍了贝叶斯垃圾邮件分类的机器学习代码,代码来源于https://www.cnblogs.com/huangyc/p/10327209.html,并对代码进行了简介。朴素贝叶斯分类器训练函数包括求p(Ci)和基于词汇表的p(w|Ci)。 ... [详细]
  • 使用freemaker生成Java代码的步骤及示例代码
    本文介绍了使用freemaker这个jar包生成Java代码的步骤,通过提前编辑好的模板,可以避免写重复代码。首先需要在springboot的pom.xml文件中加入freemaker的依赖包。然后编写模板,定义要生成的Java类的属性和方法。最后编写生成代码的类,通过加载模板文件和数据模型,生成Java代码文件。本文提供了示例代码,并展示了文件目录结构。 ... [详细]
author-avatar
45度向上倾斜的世界取_872
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有