C++实现LeetCode(167.两数之和之二 - 输入数组有序)

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

Given an array of integers that is already sorted in ascending order, 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

这又是一道Two Sum的衍生题,作为LeetCode开山之题,我们务必要把Two Sum及其所有的衍生题都拿下,这道题其实应该更容易一些,因为给定的数组是有序的,而且题目中限定了一定会有解,我最开始想到的方法是二分法来搜索,因为一定有解,而且数组是有序的,那么第一个数字肯定要小于目标值target,那么我们每次用二分法来搜索target - numbers[i]即可,代码如下:

解法一:

// O(nlgn)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int t = target - numbers[i], left = i + 1, right = numbers.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (numbers[mid] == t) return {i + 1, mid + 1};
                else if (numbers[mid] < t) left = mid + 1;
                else right = mid;
            }
        }
        return {};
    }
};

但是上面那种方法并不efficient,时间复杂度是O(nlgn),我们再来看一种O(n)的解法,我们只需要两个指针,一个指向开头,一个指向末尾,然后向中间遍历,如果指向的两个数相加正好等于target的话,直接返回两个指针的位置即可,若小于target,左指针右移一位,若大于target,右指针左移一位,以此类推直至两个指针相遇停止,参见代码如下:

解法二:

// O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return {l + 1, r + 1};
            else if (sum < target) ++l;
            else --r;
        }
        return {};
    }
};

类似题目:

Two Sum III - Data structure design

Two Sum

参考资料:

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

到此这篇关于C++实现LeetCode(167.两数之和之二 - 输入数组有序)的文章就介绍到这了,更多相关C++实现两数之和之二 - 输入数组有序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-31

C++实现LeetCode(166.分数转循环小数)

[LeetCode] 166.Fraction to Recurring Decimal 分数转循环小数 Given two integers representing the numerator and denominator of a fraction, return the fraction in string format. If the fractional part is repeating, enclose the repeating part in parentheses. Fo

C++实现LeetCode(164.求最大间距)

[LeetCode] 164. Maximum Gap 求最大间距 Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than 2 elements. Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sor

C++实现LeetCode165.版本比较)

[LeetCode] 165.Compare Version Numbers 版本比较 Compare two version numbers version1 and version2. If version1 > version2 return 1; if version1 <version2 return -1;otherwise return 0. You may assume that the version strings are non-empty and contain onl

C++实现LeetCode(163.缺失区间)

[LeetCode] 163. Missing Ranges 缺失区间 Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges. Example: Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99, Output: ["2&q

C++实现LeetCode(168.求Excel表列名称)

[LeetCode] 168.Excel Sheet Column Title 求Excel表列名称 Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example:     1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 O

C++实现LeetCode(228.总结区间)

[LeetCode] 228.Summary Ranges 总结区间 Given a sorted integer array without duplicates, return the summary of its ranges. Example 1: Input:  [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: 0,1,2 form a continuous ran

C++实现LeetCode(162.求数组的局部峰值)

[LeetCode] 162.Find Peak Element 求数组的局部峰值 A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that c

C++实现LeetCode(171.求Excel表列序号)

[LeetCode] 171.Excel Sheet Column Number 求Excel表列序号 Related to question Excel Sheet Column Title Given a column title as appear in an Excel sheet, return its corresponding column number. For example:     A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -&g

C#实现Excel表数据导入Sql Server数据库中的方法

本文实例讲述了C#实现Excel表数据导入Sql Server数据库中的方法.分享给大家供大家参考,具体如下: Excel表数据导入Sql Server数据库的方法很多,这里只是介绍了其中一种: 1.首先,我们要先在test数据库中新建一个my_test表,该表具有三个字段tid int类型, tname nvarchar类型, tt nvarchar类型 (注意:my_test表中的数据类型必须与Excel中相应字段的类型一致) 2. 我们用SELECT * FROM  OPENROWSET(

Python实现读取json文件到excel表

本文实例为大家分享了Python实现读取json文件到excel表,供大家参考,具体内容如下 一.需求 1.'score.json' 文件内容: { "1":["小花",99,100,98.5], "2":["小王",90,30.5,95], "3":["小明",67.5,49.6,88] } 2.读取json文件保存到数据库,并计算出每个人的总分和平均分 二.实现代码 import j

C#语言MVC框架Aspose.Cells控件导出Excel表数据

本文实例为大家分享了Aspose.Cells控件导出Excel表数据的具体代码,供大家参考,具体内容如下 控件bin文件下载地址 @{ ViewBag.Title = "xx"; } <script type="text/javascript" language="javascript"> function getparam() { var param = {}; param.sear = $("#sear").t

Java中excel表数据的批量导入方法

本文实例为大家分享了Java中excel表数据的批量导入,供大家参考,具体内容如下 首先看下工具类: import java.awt.Color; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.InputStream; import java.lang.ref

使用PHPExcel导出Excel表

本文实例为大家分享了PHPExcel导出Excel表的具体代码,供大家参考,具体内容如下 /** * Excel导出 * @param $fileName(文件名) * @param $headArr (表头) * @param $data (每一行的数据) * @throws \PHPExcel_Exception * @throws \PHPExcel_Reader_Exception */ function getExcel($fileName,$headArr,$data){ inclu

Python读取excel指定列生成指定sql脚本的方法

需求 最近公司干活,收到一个需求,说是让手动将数据库查出来的信息复制粘贴到excel中,在用excel中写好的公式将指定的两列数据用update这样的语句替换掉. 例如: 有个A库,其中有两个A.01和A.02字段,需要将这两个字段替换到下面的sql语句中, update A set A.01 = 'excel第一列的值' where A.02 = 'excel第二列的值' 虽然excel中公式写好了,但是还需要将总计的那行复制粘贴到txt文档中,所以索性太麻烦,果断用Python写了一个自动化

asp读取excel表名的实现代码

看代码: 复制代码 代码如下: <%@LANGUAGE="VBSCRIPT" CODEPAGE="65001"%> <% dim conn,rs,excelFileName excelFileName=Server.MapPath("Data/test.xls") set conn = Server.CreateObject("ADODB.Connection") conn.connectionstring=

Python实现对excel文件列表值进行统计的方法

本文实例讲述了Python实现对excel文件列表值进行统计的方法.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=gbk #此PY用来统计一个execl文件中的特定一列的值的分类 import win32com.client filename=raw_input("请输入要统计文件的详细地址:") flag=0 #用于判断文件 名如果不带'日'就为 0 if '\xc8\xd5' in filename:flag=1 print 50*'

在 IE 中调用 javascript 打开 Excel 表

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML> <HEAD> <META http-equiv=Content-Type content="text/html; charset=utf-8"> <TITLE>打开Excel表</TITLE> </HEAD> <BODY> <i

C#使用Ado.net读取Excel表的方法

本文实例讲述了C#使用Ado.net读取Excel表的方法.分享给大家供大家参考.具体分析如下: 微软NET提供了一个交互的方法,通过使用ADO.NET与Microsoft Office程序.可以使用内置的OLEDB来访问Excel的XLS表格.下面的例子演示了如何在C#编程读取Excel工作表.需要引用System.Data.OleDb库 using System; using System.Data.OleDb; namespace ConsoleApplication1 { class P