精华内容
下载资源
问答
  • 给定一个已按照升序排列 的有序数组,找到使得它们相加之和等于目标。 函数应该返回这个下标值 index1 和 index2,其中 index1 必须小于 index2。

    两数之和 II - 输入有序数组


    题目

    给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

    函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

    说明:

    返回的下标值(index1 和 index2)不是从零开始的。
    你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

    分析

    该题最简单最暴力的解法就是双重循环,直到找到位置,时间复杂度很高,没有充分利用题目中的条件。

    题目中已经给出:数组是升序排列的有序数组。

    这样我们就可以使用双指针来求解了:l和r分别指向数组头和尾,当l<r成立时,遍历数组,根据有序数组的特性移动指针,直到找到为止。

    代码实现

        /**
         * 167. 两数之和 II - 输入有序数组
         * @param numbers
         * @param target
         * @return
         */
        public int[] twoSum(int[] numbers, int target) {
            int l = 0, r = numbers.length - 1;
            int[] res = new int[2];
            while (l < r){
                if (numbers[l] + numbers[r] == target){
                    res[0] = l + 1;
                    res[1] = r + 1;
                    break;
                }else if (numbers[l] + numbers[r] < target){
                    l++;
                }else {
                    r--;
                }
            }
            return res;
        }
    
    展开全文
  • 1.两数之和-Python-LeetCode

    万次阅读 多人点赞 2018-03-31 21:49:35
    刚开始接触算法方面,好多都不懂,打算每刷一题就整理一下题目:给定一个整数数列,找出其中为特定值的那。你可以假设每个输入都只会有一种答案,同样的元素不能被重用。示例:给定 nums = [2, 7, 11, 15], ...

    刚开始接触算法方面,好多都不懂,打算每刷一题就整理一下

    题目:

    给定一个整数数列,找出其中和为特定值的那两个数。

    你可以假设每个输入都只会有一种答案,同样的元素不能被重用。

    示例:

    给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

    解法一:.刚开始看到的的时候,第一个想到的就是用一个嵌套循环把nums列表遍历两次,虽然测试通过了但是耗时实在太长了,然后就考虑了其他时间复杂度低的方法

    代码如下:

    class Solution:
        def twoSum(self,nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            #用len()方法取得nums列表的长度
            n = len(nums)
            #x取值从0一直到n(不包括n)
            for x in range(n):
                #y取值从x+1一直到n(不包括n)
                #用x+1是减少不必要的循环,y的取值肯定是比x大
                for y in range(x+1,n):
                    #假如 target-nums[x]的某个值存在于nums中
                    if nums[y] == target - nums[x]:
                        #返回x和y
                        return x,y
                        break
                    else:
                        continue

    解法二:用一个for循环,直接在里面查询target-nums[x]是否存在于nums列表中,速度比解法一快了许多,但还是不够

    代码如下:

    class Solution:
        def twoSum(self,nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            #用len()方法取得nums列表长度
            n = len(nums)
            #x从0到n取值(不包括n)
            for x in range(n):
                a = target - nums[x]
                #用in关键字查询nums列表中是否有a
                if a in nums:
                    #用index函数取得a的值在nums列表中的索引
                    y = nums.index(a)
                    #假如x=y,那么就跳过,否则返回x,y
                    if x == y:
                        continue
                    else:
                        return x,y
                        break
                else :
                    continue


    解法三:这个解法是我看了排名前几个的答案后才知道的, 先创建一个空字典,然后依次把target-nums[x]的值存入字典,存入一个就跟nums[x+1]去比较, 字典中的key为target-nums[x],value为x,也就是nums[x]在nums列表中的索引位置。当字典d中有nums[x+1]时,也就是target - nums[y] = nums[x+1] , y肯定是小于x+1的(因为y是x+1之前循环过的数字)

    所以是 return y,x+1

    class Solution:
        def twoSum(self,nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            #用len()方法取得nums列表长度
            n = len(nums)
            #创建一个空字典
            d = {}
            for x in range(n):
                a = target - nums[x]
                #字典d中存在nums[x]时
                if nums[x] in d:
                    return d[nums[x]],x
                #否则往字典增加键/值对
                else:
                    d[a] = x
            #边往字典增加键/值对,边与nums[x]进行对比
    
            
                        
                        

    展开全文
  • LeetCode第一题:两数之和-C++

    万次阅读 2018-05-28 16:43:51
    =i) {// 如果目标值减去循环到的值对应的下标不为0,或者不为i,【存在有另一个与循环值相加等于target,则返回结果】 twoSum.push_back(i); twoSum.push_back(tmpmap[target - nums[i]]); break; } } ...

    自己的解答(简单的遍历所有可能的组合,找到最终的结果):

    【不是特别熟悉C++,先有一个vector的插入:vector.puch_back(),主要是各种运用的不熟练,希望能有改进】
    给出简单代码:
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> twoSum;
            for(int i=0;i<nums.size();i++){
                for(int j=i+1;j<nums.size();j++){
                    if((nums[i]+nums[j])==target){
                        twoSum.push_back(i);
                        twoSum.push_back(j);
                    }
                }
            }
        return twoSum;
        }
    };
    复杂度分析:

    -时间复杂度: O(n2), 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n)O(n)O(n)的时间。因此时间复杂度为 O(n2)。
    -空间复杂度: O(1)。

    二、官方优化:
    //C++ hash_map 用法示例:
    #include <map>
    #include <string>
    using namespace std;
    
    map<string, string> namemap;
    //增加。。。
    namemap["岳不群"]="华山派掌门人,人称君子剑";
    namemap["张三丰"]="武当掌门人,太极拳创始人";
    namemap["东方不败"]="第一高手,葵花宝典";
    
    //查找。。
    if(namemap.find("岳不群") !=namemap.end()){ ...}

    --哈希表:

    //哈希表

    vector<int> twoSum(vector<int>& nums, int target) {
          vector<int> twoSum;
          map<int, int> tmpmap;//键值为nums的值,变量值为nums下标
            for (int i = 0; i < nums.size(); i++) {
              tmpmap[nums[i]] = i;
          }
          for (int i = 0; i < nums.size(); i++) {
              if (tmpmap.count(target - nums[i]) != 0 && tmpmap[target-nums[i]]!=i) {//  如果目标值减去循环到的值对应的下标不为0,或者不为i,【存在有另一个数与循环值相加等于target,则返回结果】
                twoSum.push_back(i);
                  twoSum.push_back(tmpmap[target - nums[i]]);
                  break;
              }
          }
          return twoSum;
      }  

    --哈希表优化版:

    vector<int> twoSum(vector<int>& nums, int target) {  
        vector<int> twoSum;  
        map<int, int> tmpmap;//键值为nums的值,变量值为nums下标  
      
        for (int i = 0; i < nums.size(); ++i) {  
            if (tmpmap.count(nums[i]) != 0) {  
                twoSum.push_back(tmpmap[nums[i]]);  
                twoSum.push_back(i);  
                break;  
            }  
            tmpmap[target - nums[i]] = i;  
        }  
        return twoSum;  
    }  

    展开全文
  • Python - 两数之和

    千次阅读 2019-06-07 15:23:23
    给定列表a和一个目标值target,求列表中两数之和为target的值的索引; a = [1,5,6,8,9,4,5,6,3,2,1,7,5,6,9,8,4,5,6,2,1,0,1,2,0,1,2,5,9,10] b = [11,55,88,99,66,4,77,33,22,1,6,12,35] 穷举(适应性强) ...

    给定列表a和一个目标值target,求列表中两数之和为target的值的索引;

    a = [1,5,6,8,9,4,5,6,3,2,1,7,5,6,9,8,4,5,6,2,1,0,1,2,0,1,2,5,9,10]
    b = [11,55,88,99,66,4,77,33,22,1,6,12,35]



    穷举(适应性强) 

    def x(nums,target):
        result = []
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] == target:
                    result.append((i+1,j+1))
        return result
    #print(x(b,10))

    双指针(仅限于非重复有序列表的查询)

    def y(nums,target):
        result = []
        start = 0
        end = len(nums)-1
        while start < end:
            if nums[start] + nums[end] == target:
                result.append((start+1,end+1))
                end -= 1
                start += 1
            elif nums[start] + nums[end] > target:
                end -= 1
            elif nums[start] + nums[end] < target:
                start += 1
        return result
    # print(y(sorted(b),10))

    哈希字典查找(仅限于非重复列表的查询)

    def z(nums,target):
        result = []
        dict_y = {}
        for i in range(len(nums)):
            m = nums[i]
            if target-m in dict_y:
                result.append((dict_y[target-m]+1,i+1))
            dict_y[m] = i
        return result
    #print(z(b,10))

    使用字典进行存储(仅限于非重复列表的查询)

    def h(nums,target):
        result = []
        xxx = []
        for i in range(len(nums)):
            if target-nums[i] in result:
                xxx.append([result.index(target-nums[i])+1,i+1])
            else:
                result.append(nums[i])
        return xxx
                
    print(h(b,10))

     

    展开全文
  • Python求解两数之和

    千次阅读 2019-07-01 13:32:48
    给一个列表,并且给一个目标数字,如果列表里的个数字之和等于目标数字,返回那个数字的索引值。 比如,给定列表[3,5,7,14],目标数字是10,那么返回[0,2],0是3的索引,2是7的索引,3+7=10. 注意,不可以重复...
  • 【c语言】求两数之和

    万次阅读 2019-09-08 14:16:48
    · #include int main(void) //void表示程序无返回值,'void main()'是省略写法 { //手动输入个整数(-10000 , b) int a, b; printf(“please input two numbers a and b: ”); scanf("%d%d", &a, &b); printf...
  • html+js 计算两数之和 (简洁易懂)

    千次阅读 2019-06-13 19:26:23
    计算两数之和 <!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <title></title> <script type="text/javascript"> window.οnlοad=function...
  • 给定一个整数一个目标值,找出数组中和为目标值的。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums...
  • 题目:给定一个整数数列,找出其中为特定值的那。 你可以假设每个输入都只会有一种答案,同样的元素不能被重用。 有三种思路: 第一个思路:遍历数组i从第一个开始,j从(i+1)开始,直到找到合适的值...
  • 两数之和 给定一组整数,还有一个目标数,在给定这组整数中找到两个数字,使其和为目标数,如找到,解是唯一的。找不到则显示 “no answer”。输出的下标按从小到大排序。用一重循环加字典实现。 输入格式: 在一行中...
  • //分别求出整型数的两数之和和浮点数的两数之和,并在主函数中调用。 #include&lt;iostream&gt; using namespace std; template&lt;typename T&gt; T add(T a, T b) { T c; c = a + b; return c; ...
  • leetcode 1两数之和(python3实现)

    万次阅读 2019-11-30 13:59:26
    两数之和: 题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样...
  • 两数之和 IV - 输入 BST

    万次阅读 2020-06-28 13:48:55
    两数之和 IV - 输入 BST(力扣:653) 给定一个二叉搜索树和一个目标结果,如果 BST 中存在两个元素且它们的和等于给定的目标结果,则返回 true。
  • Java实现 LeetCode 167 两数之和 II - 输入有序数组

    万次阅读 多人点赞 2020-02-23 10:06:14
    167. 两数之和 II - 输入有序数组 给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。 说明: 返回的下标值...
  • C语言:求的最大公约数最小公倍数

    万次阅读 多人点赞 2019-06-19 16:31:03
    两数为ab(a>b),用a除以b,得a÷b=商…余数,若余数为0 ,则最大公约数为b;若余数不为0 ,则再用b÷余数, 得b÷余数=商1…余数1,若余数1=0,则最大公约数为余数,若余数1不为0,继续让商÷余数n,一直到能够...
  • # 赋值3个参数,因为都是str,所以sum需要float转换一下 ...print('这个数字的和是%f' %(float(input('请输入数字1:'))+float(input('请输入数字2:')))) # 使用%f格式化输出,1条语句解决问题  
  • 给定一个数组,求数之和=给定值sum的所有组合个数。 【变形】数之和=sum的任意一组数 【方法一】穷举法 从数组中任意找个数,看其和是否=sum。时间复杂度O(N^2) 【方法二】先排序,然后定义个指针,...
  • 给定任意个整数,求个整数范围内的所有整数累加。 1.需求分析: (1)任意给定个整数,考虑函数封装来传参。 (2)函数内容即为累加的求法,参考while循环求1-100以内的整数数字累加方法。 2.代码块: ...
  • 力扣第1题--(两数之和)的优解

    万次阅读 2020-10-21 04:25:27
    力扣第一题(两数之和) class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { ...
  • # 1、输入个整数,输出两者之和与两者之商 a = int(input('请输入被除:')) b = int(input('请输入除数:')) print(a+b) print(a/b) print(a*b)
  • 167. 两数之和 II - 输入有序数组

    千次阅读 2019-04-12 00:20:05
    给定一个已按照升序排列的有序数组,找到使得它们相加之和等于目标。 函数应该返回这个下标值 index1 和 index2,其中 index1必须小于index2。 说明: 返回的下标值(index1 和 index2)不是从零开始的...
  • #include <stdio.h> #include <stdlib.h> void sum_diff(float op1, float op2, float *psum ,float *pdiff) ; int main() ... float data1 , data2 ,sum , diff,*psum ,*pdiff ;... psum = &...
  • 从键盘输入,求它们的并输出 (30分) 本题目要求读入2个整数AB,然后输出它们的。 输入格式: 在一行中给出一个被加 在另一行中给出一个加 输出格式: 在一行中输出值。 输入样例: 在这里给出一组...
  • 快速找出一个数组中的个数字,让这个数字之和等于一个给定的值,为了简化起见,我们假设这个数组中肯定存在至少一组符合要求的解。  假如有如下的个数组,如图所示:  5,6,1,4,7,9,8  
  • //从键盘输入,求两者的并输出 public class lolo { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int i=1; int b=2; System.out.println("i+b="+...
  • java求相加代码

    万次阅读 2018-01-27 12:59:52
    假定目前Java环境已经构建完成,然后在编辑器中输入如下一段代码,编译运行,即可实现从控制台输入个整数,并对其求和将结果输出到控制台。 import java.util.*; class HelloWorld{ public static void main...
  • 自学C语言编程第一个/求

    千次阅读 2016-01-21 14:55:32
    任务代码:/* ...*All rights reserved. *文件名称:main.c *作者:行者-胤临 *时间;2016年1月20号 *版本号:V1.0 ...*程序输出:求 */ #include int main() { int a,b,sum; scanf("%d%d",&a,&b)
  • 指针调用函数求两数和与差

    万次阅读 2014-12-04 23:46:48
    输入代码: /* ... * All rights reserved. * 文件名称:sum123.cpp * 作 者:林海云 ... * 问题描述:输入两个整数,调用函数ast后,输出了两数之和及两数之差。 * 输入描述:两个数 * 程序输出:两数
  • C语言编程之求个整数之和

    万次阅读 2019-05-27 19:28:12
    个整数之和。 解题思路:设置三个变量,a和b用来存放个整数,sum用来存放和数。用赋值运算符“=”把相加的结果传送给sum. 代码: #include<stdio.h> int main(){ int a,b,sum; a=123; b=456; sum=a+b; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,549,939
精华内容 2,219,975
关键字:

两数之和