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++实现两数之和之二 - 输入数组有序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 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++实现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(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(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++实现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(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(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(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++实现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 t

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode（三数之和）

    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut

  • C++实现LeetCode(18.四数之和)

    [LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be

  • JS求解两数之和算法详解

    本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法 利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num

  • C++实现LeetCode(29.两数相除)

    [LeetCode] 29. Divide Two Integers 两数相除 Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate

  • 使用python实现两数之和的画解算法

    使用python实现两数之和的画解算法

    题目描述 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],

  • c语言如何实现两数之和

    c语言如何实现两数之和

    目录 c语言实现两数之和 c语言中比较两数大小 题目要求 分析一下 c语言实现两数之和 int *twoSum(int *nums , int numsSize , int target , int *returnSize) { int i = 0 , j = 0; *returnSize = 2; int *a = (int *)malloc(sizeof(int) * 2); for(i = 0;i<numsSize;i++) { for(j=i+1;j<numsSize;j++) { i

  • C++实现LeetCode(113.二叉树路径之和之二)

    [LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22,  5 / \ 4   8 /      / \ 11  13  4 /  \         / \ 7  

随机推荐